Induction proof of an identity

Question

I know how to prove this identity using combinatorics. However I want to use induction to prove it now. I know I can use the help of this property:

Can you provide a start up/push so that I can continue go on from there?

Answer 1

Let $m$ be the variable with which you do the induction proof. The base case is when $m=n$ where we get $$\sum_{j=n}^{n}\binom{j}{n}=\binom{n}{n}=1$$ And we see that $\binom{n+1}{n+1}$ also is equal to $1$. Thus, the base case is cleared.

Now we assume that $$\sum_{j=n}^{m}\binom{j}{n}=\binom{m+1}{n+1}$$ What we need to do is to prove, that using this assumption, the following is true: $$\sum_{j=n}^{m+1}\binom{j}{n}= \underbrace{\sum_{j=n}^{m} \binom{j}{n}}_{\binom{m+1}{n+1}} + \binom{m+1}{n} = \binom{m+2}{n+1} $$ Let's use the property you mentioned to now show this. The property as it's stated (I used $a$ and $b$ to not use $n$ again to avoid confusion) in your picture is $$\binom{a-1}{b-1}+\binom{a-1}{b}=\binom{a}{b}$$ We apply the property to our problem by saying $a-1=m+1$ and $b-1=n$, which imply $a=m+2$ and $b=n+1$ thus $$\binom{m+1}{n} + \binom{m+1}{n+1}=\binom{a-1}{b-1}+\binom{a-1}{b} \\ =\binom{a}{b} = \binom{m+2}{n+1}$$

This completes our proof. Hopefully that should help.