# Prove an inequality by Induction: $(1-x)^n + (1+x)^n < 2^n$

Could you give me some hints, please, to the following problem.

Given $x \in \mathbb{R}$ such that $|x| < 1$. Prove by induction the following inequality for all $n \geq 2$:

$$(1-x)^n + (1+x)^n < 2^n$$

$1$ Basis:

$$n=2$$ $$(1-x)^2 + (1+x)^2 < 2^2$$ $$(1-2x+x^2) + (1+2x+x^2) < 2^2$$ $$2+2x^2 < 2^2$$ $$2(1+x^2) < 2^2$$ $$1+x^2 < 2$$ $$x^2 < 1 \implies |x| < 1$$

$2$ Induction Step: $n \rightarrow n+1$ $$(1-x)^{n+1} + (1+x)^{n+1} < 2^{n+1}$$

$$(1-x)(1-x)^n + (1+x)(1+x)^n < 2·2^n$$ I tried to split it into $3$ cases: $x=0$ (then it's true), $-1<x<0$ and $0<x<1$.

Could you tell me please, how should I move on. And do I need a binomial theorem here?

-
Could you kindly typeset your question? It is very hard to read what you have written. –  user17762 Oct 18 '11 at 22:43
Sorry, Sivaram Ambikasaran. Could you tell me, please, how do you type the formulas the way you do it? I tried to use codecogs.com/latex/eqneditor.php, but it didn't worked somehow. –  Lissa Oct 19 '11 at 10:33

You "basis" proof is upside down: you should start with what is known and work towards what you want to prove.

Can you see $(1-x)^n$ and $(1+x)^n$ are each positive if $|x| < 1$? And $(1-x)$ and $(1+x)$ are each less than $2$?

So $(1-x)^{n+1}+(1+x)^{n+1} < 2(1-x)^{n}+2(1+x)^{n}$ and you should be able to complete the induction.

-
Thanks! I got it! =) –  Lissa Oct 19 '11 at 10:30

Hint: For the induction step, you assume $(1-x)^n+(1+x)^n<2^n$. You want to prove that $(1-x)^{n+1}+(1+x)^{n+1}<2^{n+1}$ If you multiply both sides of the first inequality by $(1-x)+(1+x)=2$ what happens?

-
So, it's like we are going from the original inequality to the IS, right? If I multiply the first inequality, then I get: (1-x)^{n+1}+(1+x)^{n+1} + 2((1-x)^{n}+(1+x)^{n})<2\cdot 2^{n} Second part is positive, as (1-x)^{n} positive, and (1+x)^{n}, so it means, that if the whole left hand side is smaller than right hand side and both summands are positive, the both of them separately are especially smaller than the right hand side. And so we get: (1-x)^{n+1}+(1+x)^{n+1} < 2\cdot 2^{n} = 2^{n+1} Right? –  Lissa Oct 19 '11 at 7:11
Could you tell me please, how do you type those formulas the way you did it? –  Lissa Oct 19 '11 at 7:19
@Lissa: The formulas are typed in $\LaTeX$ enclosed in dollar signs. There are guides on the web. You can right-click any formula, choose Show Source, and you will see how it is done. –  Ross Millikan Oct 19 '11 at 12:54
ach so!!! Thanks! –  Lissa Oct 19 '11 at 17:21
@ So, it's like we are going from the original inequality to the IS, right? If I multiply the first inequality, then I get: $(1-x)^{n+1}+(1+x)^{n+1} + 2((1-x)^{n}+(1+x)^{n})<2\cdot 2^{n}$ Second part is positive, as $(1-x)^{n}$ positive, and $(1+x)^{n}$, so it means, that if the whole left hand side is smaller than right hand side and both summands are positive, the both of them separately are especially smaller than the right hand side. And so we get: $(1-x)^{n+1}+(1+x)^{n+1} < 2\cdot 2^{n} = 2^{n+1}$ Right? –  Lissa Oct 19 '11 at 17:23

Hint: For the induction step, use the fact that

$$(1-x)^{n+1}+(1+x)^{n+1}$$ is equal to $$[(1-x)^n+(1+x)^n][(1-x)+(1+x)]-[(1-x)(1+x)^n+(1+x)(1-x)^n].$$

-
Your hint overshoots the writeable area. Can you split it into two lines? –  user17762 Oct 18 '11 at 22:59

The proof by induction is natural and fairly straightforward, but it’s worth pointing out that induction isn’t actually needed for this result if one has the binomial theorem at hand:

Corrected:

\begin{align*} (1-x)^n+(1+x)^n &= \sum_{k=0}^n\binom{n}k (-1)^kx^k + \sum_{k=0}^n \binom{n}k x^k\\ &= \sum_{k=0}^n\binom{n}k \left((-1)^k+1\right)x^k\\ &= 2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}x^{2k}\\ &< 2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}\tag{1}\\ &= 2\cdot 2^{n-1}\tag{2}\\ &= 2^n, \end{align*} where the inequality in $(1)$ holds because $|x|< 1$, and $(2)$ holds for $n>0$ because $\sum\limits_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}$, the number of subsets of $[n]=\{1,\dots,n\}$ of even cardinality, is equal to the number of subsets of $[n]$ of odd cardinality.

-

Just show that $a^n + b^n \le (a+b)^n$ ( i guess you can use induction here too because if $p>0$ and $q>0$ we have $p+q>0$)

since $a,b$ are positive in the case

after expansion you get

$\sum_{i=1}^{n-1} \frac{n!}{i!(n-i)!} a^i b^{n-i}>0$ Which is obviously true

-