1

Prove for an even $n$,

$$ \binom{n}{0}-2 \binom{n}{1} + 2^2 \binom{n}{2} - \cdots + 2^n \binom{n}{n} = 1$$

I know induction but I don't think it will work since it's only true for even $n$? Substituting an odd $n$, the result comes out to be $-1$

P.S – this is a homework problem. I'm meant to do it on my own. So I'd really appreciate hints. Please note that this is high school level problem, so I don't know of any badass proving methods like y'all. Just couple of basics like induction and contradiction. Thanks!

William
  • 4,893
  • 1
    You may use induction in the following form: $\mathcal{P}(0)\wedge(\mathcal{P}(2n)\to\mathcal{P}(2n+2))\to \forall n,,\mathcal{P}(2n).$$ – Jack D'Aurizio Aug 17 '18 at 19:56
  • 1
    The fact that you need to prove only for even $n$ doesn't mean you can't use induction. The base will be $n=2$, the induction step will be from $n$ to $n+2$. – Mark Aug 17 '18 at 19:57
  • To make it clearer, write $n = 2k$. Then you'd be doing induction on $k = 0,1, \cdots$ the normal way. The result will be inducting on $n = 0,2,4, \cdots$. – aras Aug 17 '18 at 19:58
  • @Mark Holy cow, I didn't think of that!!!! – William Aug 17 '18 at 19:58
  • Anyway, you don't need induction for this exercise. Do you know the binomial theorem? – Mark Aug 17 '18 at 19:59
  • @Mark yep, I have a good deal of knowledge and practice with that theorem. Are you suggesting there's a way to use that somehow? – William Aug 17 '18 at 20:00
  • @InterstellarProbe Aaah! Don't give it away! OP asked for hints! – aras Aug 17 '18 at 20:02
  • Sorry! I deleted it. – SlipEternal Aug 17 '18 at 20:02
  • @InterstellarProbe Ohhhh I see what you did there. You saw a pattern $2,2^2, 2^3 $ so the other term must be $ 1$. Brilliant!!!! Thanks – William Aug 17 '18 at 20:03
  • @InterstellarProbe Thanks...though it looks like the person who just posted an answer didn't get the memo. – aras Aug 17 '18 at 20:03
  • @aras, there was almost no way to give hints here to be honest. I said to think about binomial theorem, anything more than that would be just to write the solution. – Mark Aug 17 '18 at 20:04
  • 1
    @Mark Yeah...I think saying "binomial theorem" is a perfect hint, but writing $(1-2)^n$ is a bit much. It is personal preference, maybe I was too quick to react. Would have been fun to see OP figure it out themselves. But whatever. – aras Aug 17 '18 at 20:06

2 Answers2

1

$$\left(1-x\right)^n= \sum_{k=0}^n \binom{n}{k}(-x)^k$$

With $x=2$ and $n$ even.

mathcounterexamples.net
  • 70,018
  • Just confirming, you would actually have to mention $n$ is even while writing the proof right? Cuz if I dont, then $n$ could be taken to be $n \in \mathbb{N} $by default? – William Aug 17 '18 at 20:06
1

Given n is even.

$$(1-x)^n=\binom{n}{0}-x\binom{n}{1}+x^2\binom{n}{2}-x^3\binom{n}{3}+\cdots +x^n\binom{n}{n}$$

put $$x=2$$ $$(1-2)^n=\binom{n}{0}-2\binom{n}{1}+2^2\binom{n}{2}-2^3\binom{n}{3}+\cdots +2^n\binom{n}{n}$$ $$\binom{n}{0}-2\binom{n}{1}+2^2\binom{n}{2}-2^3\binom{n}{3}+\cdots +2^n\binom{n}{n}=(-1)^n=1$$

since $n$ is even $(-1)^n=1$

Deepesh Meena
  • 4,408