Question

prove n>equal to 5, 4n<2^n

Answer 1

since n \(\ge\) 5, we can plug 5 in for n.

\(\large 4(5) < 2^5 \iff 20 < 32\)

Answer 2

If you think about it, \(\large 2^n\) is a function that is approaching \(+ \infty\) much,much faster than \(4n\), therefore all the numbers from 5 onwards are going to respectively represent the difference in these function's increase.

Answer 3

its for a proofs class I need to show this through induction

Answer 4

Ohh I see....

Answer 5

Okay, lets do some mathematical induction.

Answer 6

Prove 4n < 2^n, for all n >= 5.

Answer 7

Base case. n = 5. 4*5 = 2- <= 2^5 = 32 is true.

Answer 8

Induction step.
Assume 4n <= 2^n is true.
Plug in (n+1) for n. 4(n+1) <= 2^(n+1).
4n + 4 <= 2*2^n
4n <= 2*2^n - 4
Now compare 2^n and 2*2^n - 4 (for n>=5).

We can use induction a second time to prove that 2^n <= 2*2^n - 4 for all n>=5.
Base case, n=5. 2^5 = 16 <= 2*2^5 - 4 = 28 is true.
Induction step, Assume 2^n <= 2*2^n - 4 for all n>=5 is true. Plug (n+1) for n.
2^(n+1) <= 2*2^(n+1) - 4
2*2^n <= 4*2^n - 4
Divide both sides of the inequality by 2.
2^n <= 2*2^n -2
We know that 2*2^n - 4 <= 2*2^n - 2 is true, and since we assume 2^n <= 2*2^n - 4 we know the following is also true: 2^n <= 2*2^n - 4 <= 2*2^n - 2.
This means that 2^n <= 2*2^n - 2 is true, which implies 2^(n+1) <= 2*2^(n+1) - 4 is true.
By mathematical induction we conclude that 2^n <= 2*2^n - 4 is true for n>=5.

Now, back to our original induction proof.
Since we now know 2^n <= 2*2^n - 4, we can combine this with our assumption that 4n <= 2^n to get the following: 4n <= 2^n <= 2*2^n - 4. This means 4n < 2*2^n - 4, which implies 4(n+1) <= 2^(n+1) is true for n>=5.
Therefore, by strong induction (using induction twice), we conclude 4n <= 2^n is true for all n >= 5.