I don't remember how to prove that sum using a block walking argument. I have searched the net and can find no demonstration of it. Looking through my own library now, if I find it I will post it.
Nearest thing is:
http://server251.theory.cs.cmu.edu/twiki/bin/view/Main/CountingThree
goto summing and squaring in pascals triangle.
This is related to block walking because the numbers in pascals triangle correspond to the number of ways to reach each lattice point of a 2X2 grid. His demonstration is not a proof though. just evidence to suggest your sum.
]]>Block walking is the actual walking of paths on a 2D lattice. It is similar to walking in a city with a rectangular grid of streets. Many sums and recurrences that occur in combinatorics can be evaluated and proved using it.
]]>The proof is difficult and I am sorry that I can not provide an easier one.
The series can be rewritten like this.
We prove this with a combinatorial argument. If we want to select n things out of 2n things we could separate the things into 2 piles each with n things in them.
There are
ways to select k things from the first pile and ways to take n-k objects from the second pile to make up a selection of n things. So the number of ways to make the selection isThis is out of an Introduction to Combinatorics by C.L. Liu a horrible book. It is the only proof I know that uses a combinatorial argument. There is another proof that uses generating functions but it is even tougher.
]]>