Math Induction Prove using math Induction: Binomial Coefficient: (n 0) + (n 1) + (n 2) + (n n) = n^2.?

Question

Please prove using Math induction...

Answer 1

Equation is: (n 0) + (n 1) + ... = 2^n

For n = 0, (n 0) = (0 0) = 0!/(0!)^2 = 1 = 2^0 [0! is taken as 1]
For n = 1, (n 0) + (n 1) = (1 0) + (1 1) = 2^1

Say this holds upto n = m. So this holds for n = m-1,m-2...

Hence (m 0) + (m 1) + ... + (m m) = 2^m

(n+1 r) = (n r) + (n r-1) for r>=1 and r<=n... prove it yourself.

So, (m+1 0) + (m+1 1) + ... + (m+1 m+1)

= (m+1 0) + [ (m 1) + ... + (m m)] + [(m 0) + (m 1) + ... + (m m-1)] + (m+1 m+1)

= 1 + [2^m - (m 0)] + [2^m - (m m)] + 1

=2*2^m + 2 - 2

= 2^(m+1)

Hence the relation holds for n=m+1 if it holds for n=m. Hence proved.

Answer 2

It's not n^2, it's 2^n.....

Induction is not a good solution here. Just observe that the binomial coefficients are the coeficients of

(x + y)^n = (n 0)x^n y^0 + (n 1) x^(n-1) y......+ (n n) x^0 y^n

Put x = y = 1 and, presto!, you get

(n 0) + (n 1) + (n 2) + (n n) = 2^n

Answer 3

FIrst it can easily be done without induction. And it is 2^n as the first answerer said. Consider the binomial expansion of
(1 + x)^n = ∑{i=1,n} (n i) x^n
Now set x = 1 and we get
2^n = (n 0) + (n 1) + ... (n n)