Show that $\sum_{i=0}^{n}\binom{k}{i}=2^{k-1}$

Question

Show that $$\sum_{i=0}^{n}\binom{k}{i}=2^{k-1}$$ for every positive odd integer in the form of $k=2n+1$ ($n$ being a positive integer).

I tried the usual induction demonstration.

The case for $k=1$ is rather trivial. I'm currently stuck at the second part of the proof. I know that $\binom{k}{0}=1$ for every $k$ and $$ \sum_{i=0}^{n} \binom{n}{i} = 2^n$$ but despite that I'm having trouble arriving at the desired result.

Other duplicates: (1) Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$; (2) Prove the identity $\binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n} = 4^n$; (3) Find the value of $\sum_{k=0}^{n}C(2n+1,k)$?; (4) Proving combinatoric identity; (5) Proof involving binomial sums. — The Amplitwist, Feb 04 '22 at 21:41
Other duplicates (contd.): (6) Problem proving $\sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2}$; (7) prove $\sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$; (8) Prove identity based on binomial theorem; (9) Closed form of $\sum\limits_{k=0}^{n} {2n+1 \choose k}$; (10) difficulties in a proof with binomial theorem. — The Amplitwist, Feb 04 '22 at 21:46
Other duplicates (contd.): (11) Combinatorics Proof for $\sum_{k=0}^{n} \binom{2n+1}{k}=2^{2n}$; (12) Combinatorical proof $\sum\limits_{k=0}^n{{2n+1}\choose k}=2^{2n}$; (13) Proving binomial sum using mathematical induction. — The Amplitwist, Feb 04 '22 at 21:55

score -1 · Answer 1 · answered Feb 04 '22 at 21:51

This follows from the symmetry in the rows of Pascal's Triangle.

Namely, the last $n+1$ numbers in row $k=2n+1$ of Pascal's Triangle are just the first $n+1$ numbers in reverse order, and so the sum of the first $n+1$ numbers ($\binom{k}{0}$ to $\binom{k}{n}$) is half of the sum of all the numbers in row $k$, which is equal to $\frac{1}{2} \cdot 2^k=2^{k-1}$.

Show that $\sum_{i=0}^{n}\binom{k}{i}=2^{k-1}$

1 Answers1