2

the problem is:

Prove by induction. In each case, n is a positive integer.

$2^{n} ≤ 2^{(n+1)} - 2^{(n-1)} - 1$

Right now I am at the following, but I got stuck and don't know where to go from here.

$2^{(n+1)} ≤ 2^{(n+2)} - 2^{n} - 1 = 2^{n}(2^{2} - 1) - 1 = 2^{n}(3) - 1 =$ $3*2^{n} - 1$

allizdog
  • 897
Kevin doesmath
  • 137
  • This is not how induction works. You need to use the formula in itself to reach the next level, in this case use the inquality to expand $2^{(n+1)}$ and $2^{(n-1)}$. Don't forget to prove the base case $n=1$. – jgyou Nov 03 '16 at 03:18
  • @jgyou So in other words I should start from the inequality in the problem, and work towards showing $2^{(n+1)} ≤ 2^{(n+2)} - 2^{n} - 1$ ? What do you mean by expanding those two terms? How would I do that? – Kevin doesmath Nov 03 '16 at 03:25

2 Answers2

2

Obviously you need to show the inequality holds for $n=1$ which is trivial. Then suppose you have $2^n \leq 2^{n+1}-2^{n-1}-1$ for some $n$. Multiplying everything by 2 you get $(2)2^n \leq (2)2^{n+1}-(2)2^{n-1}-2$ which equals to $2^{n+1} \leq 2^{n+2}-2^{n}-2 \leq 2^{n+2}-2^n-1$ so the inequality holds for $n+1$ which implies it holds for every natural number.

allizdog
  • 897
0

First, prove the base case $n = 1$:

$$2^1 \le 2^2 - 2^0 - 1 = 2$$

Now, we want to extend the equation to the $n^{th} + 1$ term. We get:

$$2^{n+1} \le 2^{n+2} - 2^n - 1$$

Working with the right side of the equation now, we can begin to simplify the expression:

$$2^{n+2} - 2^n - 1 = 2^n(4 - 1) - 1 = 3*2^n - 1$$

Dividing out $2^n$ from both sides of the expression leaves us with this:

$$2 \le 3 - \frac {1}{2^n}$$

This inequality will always hold true for $n \ge 1$, as the base case $n = 1$ leaves us with $2 \le 2$, and as $n$ increases, the amount being subtracted off of $3$ will only decrease.

Derek Ehle
  • 196