Question

Prove by induction that for all n >= 0, n choose 0 + n choose 1 + ... + n choose n = 2^n. In the inductive step, use Pascal’s identity.

Answer 1

What is Pascal's identity?

Answer 2

(n+1 choose k) = (n choose k-1) + (n choose k)

Answer 3

\[
\sum_{k=0}^{n+1}\binom{n+1}k=\binom {n+1}k+\sum_{k=0}^n\binom {n+1}k
\]

Answer 4

wait, did you prove pascal's identity or my question?

Answer 5

We don't need to prove pascal's identity.

Answer 6

I'm just getting you a little closer to the inductive hypothesis.

Answer 7

i still can't figure it out

Answer 8

Well, first use pascals identity here.