1
$\begingroup$

I did the following base case $n = 5$ $\begin{align*} 4(5) &\lt 2 ^5\\ 20 &\lt 32 \end{align*}$ So true.

$\begin{align*} 4n &\lt 2^n\\ n &\lt 2^{n-2}\\ \log_2(n)+2 &\lt n \end{align*}$ But I don't think this is right. Where do I add in the $(n+1)$.

  • 0
    yes thats what i meant n≥52012-04-12

5 Answers 5

3

The induction base is correct.

For the inductive step, we assume that the result holds for $n$, with $n\geq 5$; that is, are assuming that $4n\lt 2^n,\qquad n\geq 5.$ We want to prove that, under this assumption, $4(n+1)\lt 2^{n+1}$.

Hint the first. $4(n+1) = 4n+4 \lt 2^n+4$, with the last step using the induction hypothesis.

Hint the second. $2^{n+1} = 2\times 2^n = 2^n+2^n$.

2

Hint

So you want to show for $n>4$, $4n<2^n \implies 4n+4 < 2^n+2^n$

1

If 4n<2^n then 4n+4<2^n+4<2^n+2^n=2^{n+1} (the second inequality hold since $2^n\geq4 $ for $n\geq 2$). It follows that 4(n+1)<2^{n+1}.

0

Here is what I think might work:

Step 1: Base case. You've done this.

Step 2. Assume $4k<2^k$ for arbitrary k contained in the naturals. You can do this because your base case proves the assumption true for at least one k. That is, you've proved this true for k=5.

Step 3. Prove this holds for $n=k+1$.

$4k<2^{k}$ $8k<2^k*2$ $8k<2^{k+1}$

It is obvious that: $4k+1<8k<2^{K+1}$ for $K>4$

And therefore, by induction, that $4n<2^n$ for all n belonging to the naturals where n>4.

That is my attempt. Hope it works.

0

Given $5\leq{n}$

Assume $4n<2^n$

Prove $4(n+1)<2^{n+1}$:

  • $4(n+1)=4n+4$
  • $4n+4<2^n+4$ assumption used here
  • $2^n+4<2^n+32$
  • $2^n+32=2^n+2^5$
  • $2^n+2^5\leq2^n+2^n$ given fact used here
  • $2^n+2^n=2^{n+1}$