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

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.

• You need to use "Strong" induction in this case. First show it works for $j=0$ and $j=1$, then show if it works for $j-1$ and $j$ then it works for $j+1$. Jan 15 '20 at 21:04
• @DonaldSplutterwit Yes. But, it works only up to N-1 and not all the integers. So induction should not prove this formula. Jan 15 '20 at 21:10
• I think you are misunderstanding what the statement is claiming. It is not claiming $x_j={N\choose j}$ for all $N$ and doing induction on $N$. Is is claiming that $x_j={N\choose j}$ for all $j$ (up to $N-1$) and doing induction on $j$. Part of what is confusing you is that we are doing induction on a variable $j$ that has an upper limit, $N-1$, and so our result is not for all natural numbers but just for natural numbers from $1$ to $N$. This is okay. We can do induction for finite values. Jan 15 '20 at 21:48
• Both $x_j$ and ${N \choose j}$ are only defined for $j\le N$ so that's our upper bound. Our statement is $P(j)=$ if [$j \le N$] then [$x_j = {N\choose j}$. We can prove $P(j)$ for all natural $j$ because if $j> N$ then [$j \le N]$ is false and "if [FALSE] then $anything$" is a true statement so if $j > N$ then $P(j)=$ if [$j \le N$] then [$x_j = {N\choose j}$; is a true statement. Jan 15 '20 at 22:18
• "Nowhere do we specify an upper bound" Uh.... yes we do! ... it says "for j=1,...,N−1" in black and white!.... So induction will be successful up to $j+1 \le N$. For $j > N$ it will fail but we don't give a flying funky if it fails for values we don't care about. We only care that it is successful on the values we DO care about. ... "In this case it only holds up to N-1" For $j+1$ where $j \le N-1$. So $j+1 \le N$. And we don't CARE if it holds for any higher values? Why on earth would we? Jan 15 '20 at 22:52

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.

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$$.