Proving recurrence using induction where there is an upper limit on the number of integers to prove it for

Question

Given $x_0=1$ and $x_j=x_{j-1}\frac{N-(j-1)}{N}+x_{j+1}\frac{j+1}{N}$ for $j=1,...,N-1$, the formula $x_j={N\choose j}$ can be proven by induction. I do not see why we are able prove it by induction, seeing that using induction, we prove the base case, we assume the formula holds for n, then show it holds for n+1, then we claim it holds for every integer. In this case it only holds up to N-1. So why does the induction proof work? I think that the induction proof should fail.

The inductive proof: $x_0=1$, Suppose the result is true for $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}$$

See it works but I think that it should fail.

Answer 1

The statement is not for every positive integer but only for positive integers up to $N$. It is not trying to claim it is true for any positive integer greater than $N$.

Consider: $P(j )=$: If $j \le N$ then something, call it $Q(j)$ is true.

Let's say we can show that if $k< N$ that $Q(k)\implies Q(k+1)$ but only if $k < N$. I claim we can still prove $P(k)$ is true for all natural $k$.

Base case: $P(1)$. We show that $Q(1)$ is true and as $1 < N$ then $P(1) is true.

Induction step: $P(k)\implies P(k+1)$.

Assume if $k\le N$ then $Q(k)$ is true.

Case 1: $k \ge N$.

Then $k+1 > N$ and [$k+1 \le N$] is false: $FALSE \implies Q(k+1)$ is vacuously true whether $Q(k+1)$ is true or not. So $P(k+1)$ is true.

Case 2: $k < N$.

The $k+1 \le N$. We showed that $Q(k)\implies Q(k+1)$. So if [$k+1 \le N]\implies Q(k+1)$ is true. So $P(k+1)$ is true.

SO our induction step works.

We have proven:

For any natural $j$, $P(j)$ is true.... or in other words,

if $j \le N$ then $Q(j)$ is true... or in other words,

$Q(j)$ is true for every natural $j \le N$.

That's all the induction is trying to claim.

The induction of $Q(j)$ works..... up to $j \le N$. There is nothing invalid about this.

Answer 2

Given the recurrence you have written, you will need two initial values to get going. Solving the recurrence for $x_{j+1}$ gives $$x_{j+1} = \frac{n x_j+ (j-n-1) x_{j-1}}{j+1}.$$ Note that if $j=n$, this gives $$x_{n+1} = \frac{n\cdot 1 + (n-n-1)\cdot n}{n+1} = 0,$$ just as you would expect. So in fact the inductive proof holds for all $j$ provided you define $\binom{n}{j}=0$ for $j<0$ or $j>n$.