Question

Proving using induction Sum {i=0 to n} (n choose i) = 2^n for all n >= 0.

Ok, so the idea is to add the next term. But what is the next term?

Answer 1

k+1
∑ (k + 1 choose i) ????
i=0

Answer 2

That's exactly right. You just have to remember that one of the definitions for the binomial coefficients is\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\]

Answer 3

Derived from the Pascal's triangle

Answer 4

@kropot72 O.o is that really the definition? or a derived formula?

Answer 5

Well how do you calculate one grid in the Pascal Triangle?

Answer 6

@kc_kennylau add the number from the left to the number from the right?

Answer 7

That's exactly what the formula is doing

Answer 8

If you say that \[\binom{n}{0}=\binom{n}{n}=1\]for all positive integers \(n\), it's a perfectly valid recursive definition.

Answer 9

And the definition can be thought to be exactly equivalent to the construction of Pascal's triangle.

Answer 10

ahh I see. I was used to thinking (nCk) = n! / ( (n-k)! k! )

Answer 11

so
k+1
∑ (k + 1 choose i) is correct?
i=0

Answer 12

wait no i don't think it is O.O

Answer 13

You want to show that that sum is equal to \(2^{k+1}\) assuming \(\sum_{i=0}^k\binom{k}{i}=2^k\). If you've already shown it for \(n=0\), that would be enough finish the problem by induction.

Answer 14

but n = 0 is the base case. What about the inductive step? That's what i'm stucked on.

I know the assumption is that
(kC0) + (kC1) + ... (kCk) = 2^k for some integer k, now i need to add the next term, which is (k+1 C k) ??

Answer 15

or is it (k+1 C i) ?

Answer 16

The inductive step is assuming that\[\sum_{i=0}^k\binom{k}{i}=2^k.\]You want to show that\[\sum_{i=0}^{k+1}\binom{k+1}{i}=2^{k+1}\]somehow using the inductive hypothesis. The trick to do this, is to write each term as a sum of smaller terms using the definition of the binomial coefficients I gave above. So the first step would be\[\sum_{i=0}^{k+1}\binom{k+1}{i}=\sum_{i=0}^{k+1}\binom{k}{i}+\binom{k}{i-1}.\]You need to take a bit of care with the indices, but from this point, you should be able to apply the inductive hypothesis without too much trouble.

Answer 17

ahh I see. The "next term" in this context is the sum of the coefficient of next row in the pascal triangle. I just thought it's the next term on the current k row -.- No wonder i couldn't reach 2^(k+1).

Thank you ^.^ @KingGeorge

Answer 18

This is a nice example of what could be considered a non-standard inductive proof for exactly the reason. There's no real "next term" to add on, so you have to be a little creative with what happens when you increment \(k\).