( 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.