( The better form of the question with correct symbols is here.
http://www.geocities.com/johntyung/Q2.pdf )
*** For this problem I heard that they solved it by just using the identity and manipulating it algebraically. Without using induction. ***
for n even, prove that
(n choose 0) + (n choose 2) + (n choose 4) +...+ (n choose n)=2^(n-1)
and
(n choose 1) + (n choose 3) +...+(n choose (n-1)) = 2^(n-1)
using mathematical induction and/or various identities involving binomial coefficients.
(Hint: first establish the identity,
((m+2) choose k) = (m choose k)+ 2(m choose (k-1)) +(m choose (k-2) )
Then, when doing the induction, do a simultaneous induction on both identities.