Demostrar la recurrencia mediante inducción cuando existe un límite superior en el número de números enteros para los que se puede demostrar

Question

Dado $x_0=1$ y $x_j=x_{j-1}\frac{N-(j-1)}{N}+x_{j+1}\frac{j+1}{N}$ para $j=1,...,N-1$ la fórmula $x_j={N\choose j}$ se puede demostrar por inducción. No veo por qué podemos demostrarlo por inducción, ya que utilizando la inducción, demostramos el caso base, suponemos que la fórmula es válida para n, luego demostramos que es válida para n+1, y luego afirmamos que es válida para todos los números enteros. En este caso sólo se cumple hasta N-1. Entonces, ¿por qué funciona la prueba por inducción? Creo que la prueba de inducción debería fallar.

La prueba inductiva: $x_0=1$ Supongamos que el resultado es cierto para $k \le j$

$$\begin{align}x_{j+1} &=\frac{N}{j+1}\left(x_j-\frac{N-j+1}{N}x_{j-1}\right)\\&=\frac{N}{j+1}\left(\frac{N!}{j!(N-j)!}-\frac{N-j+1}{N}\frac{N!}{(j-1)!(N-j+1)!}\right)\\ &\text{after some simplification}\\&={N\choose{j+1}} \end{align}$$

Mira funciona pero creo que debería fallar.

Answer 1

La declaración no es para cada entero positivo pero sólo para enteros positivos hasta $N$ . No es probando para afirmar que es cierto para cualquier número entero positivo mayor que $N$ .

Considéralo: $P(j )=$ : Si $j \le N$ entonces algo, llámalo $Q(j)$ es cierto.

Digamos que podemos demostrar que si $k< N$ que $Q(k)\implies Q(k+1)$ pero sólo si $k < N$ . Afirmo que aún podemos probar $P(k)$ es cierto para todos los $k$ .

Caso base: $P(1)$ . Demostramos que $Q(1)$ es cierto y como $1 < N$ entonces $P(1) es cierto.

Paso de inducción: $P(k)\implies P(k+1)$ .

Supongamos que $k\le N$ entonces $Q(k)$ es cierto.

Caso 1: $k \ge N$ .

Entonces $k+1 > N$ y [ $k+1 \le N$ ] es falso: $FALSE \implies Q(k+1)$ es vacuamente cierto si $Q(k+1)$ es cierto o no. Así que $P(k+1)$ es cierto.

Caso 2: $k < N$ .

En $k+1 \le N$ . Demostramos que $Q(k)\implies Q(k+1)$ . Así que si [ $k+1 \le N]\implies Q(k+1)$ es cierto. Así que $P(k+1)$ es cierto.

Así que nuestro paso de inducción funciona.

Lo hemos demostrado:

Para cualquier $j$ , $P(j)$ es true.... o en otras palabras,

si $j \le N$ entonces $Q(j)$ es cierto... o en otras palabras,

$Q(j)$ es cierto para cualquier $j \le N$ .

Eso es todo lo que pretende la inducción.

La inducción de $Q(j)$ obras..... hasta $j \le N$ . Esto no tiene nada de inválido.

Answer 2

Dada la recurrencia que has escrito, necesitarás dos valores iniciales para ponerte en marcha. Resolviendo la recurrencia para $x_{j+1}$ da $$x_{j+1} = \frac{n x_j+ (j-n-1) x_{j-1}}{j+1}.$$ Tenga en cuenta que si $j=n$ esto da $$x_{n+1} = \frac{n\cdot 1 + (n-n-1)\cdot n}{n+1} = 0,$$ como era de esperar. Así que, de hecho, la prueba inductiva es válida para todo $j$ siempre que defina $\binom{n}{j}=0$ para $j<0$ o $j>n$ .