Results 1 to 2 of 2

Math Help - inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    4

    inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

    here's the specific problem I have:
    I need to show that
    \displaystyle\sum\limits_{r=0}^{n}{{n}\choose{r+1}  }{{n}\choose{r}}={{2n}\choose{n+1}}

    Here's how I got there:

    Here's the original problem, I need to prove:
    \displaystyle\sum\limits_{r=0}^k{{k}\choose{r}}^2 = {{2k}\choose{k}}
    by induction.

    I started by testing the base step and assuming that it's true for some k=n. then I set k=n+1, then expanded the sum and used Pascal's identity to get
    \sum_{r=0}^{n+1}{{n+1}\choose{r}}^2 = [{{n}\choose{0}}+{{n}\choose{-1}}]^2+[{{n}\choose{1}}+{{n}\choose{0}}]^2+[{{n}\choose{2}}+{{n}\choose{1}}]^2+...+[{{n}\choose{n}}+{{n}\choose{n-1}}]^2+[{{n}\choose{n+1}}+{{n}\choose{n}}]^2
    I distributed everything (and crossed out the terms that were 0), and got an unholy mess:
    =[{{n}\choose{0}}^2]+<br />
[{{n}\choose{1}}^2+2{{n}\choose{1}}{{n}\choose{0}}+  {{n}\choose{0}}^2]+<br />
[{{n}\choose{2}}^2+2{{n}\choose{2}}{{n}\choose{1}}+  {{n}\choose{1}}^2]+<br />
...<br />
+[{{n}\choose{n}}^2+2{{n}\choose{n}}{{n}\choose{n-1}}+{{n}\choose{n-1}}^2]+[{{n}\choose{n}}^2]
    I noticed that if I reordered the sum so that the first terms in each bracket were grouped together, the last terms in each bracket were grouped together, and the middle terms were grouped, I would have:

    <br />
\displaystyle\sum\limits_{r=0}^{n+1}{{n+1}\choose{  r}}^2 = <br />
\displaystyle\sum\limits_{r=0}^{n}2{{n}\choose{r}}  ^2+<br />
\displaystyle\sum\limits_{r=0}^{n}2{{n}\choose{r+1  }}{{n}\choose{r}}

    by my inductive hypothesis, the first summation works out to 2{{2n}\choose{n}}. If I expand out {{2n+2}\choose{n+1}}, I get 2{{2n}\choose{n}}+2{{2n}\choose{n+1}}.
    If I can show that \sum_{r=0}^{n}{{n}\choose{r+1}}{{n}\choose{r}}={{2  n}\choose{n+1}}, then I'll be done.
    I'm currently trying to work it out through another proof by induction, but I get the feeling it will lead me nowhere. Any help would be appreciated. Especially help in the form of telling me that I'm making it far more complicated than I need to.
    Also, the book says that the original problem is Lagrange's Identity, but I wasn't able to draw any obvious parallels between Lagrange's Identity and the original problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Wikipedia describes how to prove the original equality, which is formula (8), using Vandermonde's identity:
    \displaystyle{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}\hspace{20em}(*)
    I am not sure if your line of thought can be successfully continued, but it often happens in proofs by induction that one has to generalize the induction hypothesis P(n), and Vandermonde's identity seems to be precisely this generalization.

    Wikipedia gives an algebraic and a combinatorial proofs of Vandermonde's identity, but it can also be proved by induction. If we denote (*) above by P(m,n,r), then we can to prove \forall m\forall n\forall r\,P(m,n,r) by induction on n. Here, it is important to choose the induction hypothesis correctly. One option in proving \forall m\forall n\forall r\,P(m,n,r) is to fix arbitrary m and r and then use induction, i.e., to prove P(m,0,r) and \forall n\,P(m,n,r)\to P(m,n+1,r). However, according to my calculations, proving P(m,n+1,r) requires the induction hypothesis P(m,n,r') for a different r', namely, r'=r-1. Therefore, one should fix only m and then prove \forall r\,P(m,0,r) and \forall n\,[(\forall r\,P(m,n,r))\to (\forall r\,P(m,n+1,r))]. This way one gets a stronger induction hypothesis that works for all r.

    It is also possible to not fix m and use induction hypothesis \forall m\forall r\,P(m,n,r). In general, it is safer to import the universal quantifiers into the IH rather than fixing them before the induction starts.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 08:57 PM
  2. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 8th 2009, 01:11 AM
  3. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2009, 10:16 AM
  4. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 09:38 AM
  5. Ugh, another inductive proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 02:56 PM

Search Tags


/mathhelpforum @mathhelpforum