0

I have seen the solution to this problem where for the induction step we have:

$$2^{n+1} = 2 \cdot 2^n \gt 2 (n^2 + 4 n + 5) = (n + 1)^2 + 4(n + 1) + 5 + n^2 + 2 n \gt (n + 1)^2 + 4(n + 1) + 5$$

In this induction step we prove the inequality from left to right, my question is, is it possible to prove the inequality starting from $(n + 1)^2 + 4 (n + 1) + 5$. This is what I have tried:

$$(n+1)^2 + 4(n + 1) + 5 = (n^2 + 4 n + 5) + 2n + 5 \lt 2^n + 2n + 5$$

To continue I would need to prove that $2n + 5 \le 2^n$ which doesn't seem true.

My question is, are there times in a proof by induction where it is possible to prove the inequality in one direction and not in the other?

Jordi
  • 687

2 Answers2

2

We have to prove that $2^{7+n}\gt(9+n)^2+1$ which is true for $n=0$ (since $128\gt82)$. Assuming that $2^{7+n}\gt(9+n)^2+1$ for $n$ and prove us that $2^{8+n}\gt(10+n)^2+1$.

One has $2^{7+n}\gt(9+n)^2+1\Rightarrow 2^{8+n}\gt 2((9+n)^2+2$

Is it $2((9+n)^2+2\gt(10+n)^2+1$ for $n$ integer positive?

Yes it is. In fact $2(9+n)^2+2-((10+n)^2+1)=n^2+16n+63=(n+7)(n+9)$ and this product is positive except for negative values $n=-7,-8,-9$.

We are done.

Piquito
  • 29,594
1

$$p(n): \ 2^n>n^2+4n+5\\p(n+1): \ 2^{n+1}>(n+1)^2+4(n+1)+5$$you multiply $p(n)$ by $\ 2$ so $$\text{you now } \ 2^2*2>2(n^2+4n+5) \to A>B\\\text{you want to prove} \ 2^{n+1}>(n+1)^2+4(n+1)+5 \to A>C$$ if you prove $B>C$ proof is complete (because $A>B>C$) so try to prove $B>C$
$$n>7:\\ 2(n^2+4n+5)>(n+1)^2+4(n+1)+5\\ 2n^2+8n+10>n^2+2n+1+4n+4+5\\n^2+2n>0 \ \checkmark$$

Khosrotash
  • 24,922