0

Using mathematical induction prove that

$\displaystyle \sum^{n}_{k=0}\binom{2n+1}{k}=4^n$ for all $n\in\mathbb{N}$

What i try:

Let $$P(n): \sum^{n}_{k=0}\binom{2n+1}{k}=4^n$$

Put $n=1,$ We have $\displaystyle \sum^{1}_{k=0}\binom{3}{k}=4$

Which is true because $\displaystyle \binom{3}{0}+\binom{3}{1}=1+3=4$

Let we assume that $P(n)$ is true for $n=m,$ Then

$$P(m): \sum^{m}_{k=0}\binom{2m+1}{k}=4^m$$

Now i did not understand how can i prove for $n=m+1$. Help me please , Thanks

RobPratt
  • 45,619
jacky
  • 5,194
  • 2
    Well, I think it's easier to prove this identity without induction. Just note that this sum is a half of the $\sum_{k=0}^{2n+1}\binom{2n+1}{k}$ (why?), which is equal to $2^{2n+1}$. – richrow Jun 30 '20 at 12:02
  • Do you insist on induction? @richrow is right of course. – drhab Jun 30 '20 at 12:03

1 Answers1

3

hint for $k\ge2$: $$\binom{2m+3}{k}=\binom{2m+1}{k}+\binom{2m+1}{k-1} + \binom{2m+1}{k-1}+\binom{2m+1}{k-2}$$ now sum using your induction hypothesis

Peanut
  • 1,664