here's the specific problem I have:

I need to show that

Here's how I got there:

Here's the original problem, I need to prove:

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

I distributed everything (and crossed out the terms that were 0), and got an unholy mess:

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:

by my inductive hypothesis, the first summation works out to . If I expand out , I get .

If I can show that , 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.