0

enter image description here

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: enter image description here

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

Sarah cartenz
  • 181
  • 1
    If you change $m$ to $m+1$ what do you add to the sum on the left? – Mark Bennet Sep 04 '14 at 19:09
  • Do you know how to do an induction proof? The critical step is that you compare the result for $m+1$ with the result for $m$. If you want to move the left hand side from $m$ to $m+1$ you just add ${m+1\choose n}$. What happens if you add that to the right hand side? – almagest Sep 04 '14 at 19:16

1 Answers1

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.

Sheheryar Zaidi
  • 2,714
  • Okay! I understand much better now. I have a question though about the properties I can use. Now that I have (m+1 choose n+1) + (m+1 choose n). But I have to turn it into (m+2 choose n+1). I can see clearly that it is similar to the second property I stated. But how can I use it? Also if its okay, can you provide a web page about the properties of adding these coefficients. thank you – Sarah cartenz Sep 04 '14 at 19:37
  • Alright, I edited my answer and added the whole solution. Let me know if it's all understood :)

    Also, here's a website with loads of properties you might want to have a look at.

     – Sheheryar Zaidi Sep 04 '14 at 19:55
  • Thank you, i followed it step by step! And i'm grateful for your help, im looking forwards to seeing more of your solutions! – Sarah cartenz Sep 04 '14 at 20:59