1

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.

johnson
  • 482
  • 1
    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$. – Donald Splutterwit 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. – johnson Jan 15 '20 at 21:10
  • You are right ... to state the formula valid up to $N-1$ and then claim the next formula holds for every integer ... is a load of old cobblers! – Donald Splutterwit Jan 15 '20 at 21:26
  • @DonaldSplutterwit I am not sure if you are being sarcastic here. My point is that the induction proof should fail. But it actually works if you try it. – johnson Jan 15 '20 at 21:30
  • Yeah, I do like to use a bit of humour. But they do need to state that the iterative formula works for all integers. Despite this, you are right, if it does then $x_j=\binom{N}{j}$ for any integer $j$. – Donald Splutterwit Jan 15 '20 at 21:36
  • In this case, the proposition is true for all positive integers $j$ as long as we adopt the convention that $\binom{N}{j} = 0$ for $j > N$. In general though, we can use induction to prove that a statement $P(j)$ holds for $j \leq N$ by proving that the proposition $Q(j) := ((j \leq N) \implies P(j))$ holds for all positive integers $j$. – Dylan Jan 15 '20 at 21:46
  • 1
    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. – fleablood Jan 15 '20 at 21:48
  • If $P(1)$ is true. And if $P(k)$ is true for $k < M$ implies that $P(k)$ is true. Then we have done induction for a finite number of values and proven that $P(j)$ is true for all natural $j: 1\le j \le M$. That is valid even though it didn't prove for all naturals. We hit an upper bound but that's okay. – fleablood Jan 15 '20 at 21:51
  • @fleablood But how does the inductive method "know" that we have a bound at N-1. It merely assumes: show it works for n-1 and n-2. assume it works for n, show it works for n+2. Nowhere do we specify an upper bound, as in the above proof. So the inductive method proves the formula for all integers which cannot be true. – johnson Jan 15 '20 at 22:07
  • 1
    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. – fleablood Jan 15 '20 at 22:18
  • 1
    "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? – fleablood Jan 15 '20 at 22:52

2 Answers2

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.

fleablood
  • 124,253
0

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

rogerl
  • 22,399