0

I have this problem I need to prove:

Prove that for every $n\ge3$ this statement is true: $2^n\ge2n+1$

I proved this by induction and it was easy for me.
my question is about the second section of the question.

Two sequences is given: $8, 16, 32, \dots, 2^n$ and $7, 9, 11, \dots, 2n+1$

Prove that the sum of the geometric progression is bigger than the sum of the arithmetic progression.
Use Section A to prove it.

How do I prove it without using induction again? by logic I know this statement is true, but how do I write it in a formal way?

Thanks!

BeardGuy367
  • 93
  • 1
    What attempts have you done so far? Where are you stuck? It might help to review the meta read for tips on providing context in your question to better assist the community. – Jessie Apr 27 '21 at 19:29
  • 1
    From the first part: $2^3 \ge 7$, $2^4\ge 9$, $2^5 \ge 11$, ... – Martin R Apr 27 '21 at 19:32
  • I tried to use strong induction, trying to put numbers that are bigger and equal to 3 and to see if that statement is true. But my lecturer told me no induction is necessary. – BeardGuy367 Apr 27 '21 at 19:33
  • @ThomasAndrews Yes, thank you, I fixed the text, I'm new to the site and I messed up the question. – BeardGuy367 Apr 27 '21 at 19:36
  • You can show that the sum of the exponential series is $2^{n+1}-8$ and the sum of the arithmetic series is $(n+1)^2-9.$ – Thomas Andrews Apr 27 '21 at 19:39
  • 1
    @BeardGuy367 I don't think you can avoid induction driving your argument at some level, but I think your lecturer is saying you can hand-wave it a bit. Such as, "Because $2i + 1 \le 2^i$ for $i \ge 3$, we have $\sum_{i=3}^n (2i + 1) \le \sum_{i=3}^n 2^i$", or something similar. – Theo Bendit Apr 27 '21 at 19:40
  • @TheoBendit Yes I think I'll go with that, I will write a verbal solution to this problem. I wanted to see if my logic is correct. Than you! – BeardGuy367 Apr 27 '21 at 19:48

1 Answers1

1

Claim: $$ \sum_{n=3}^k 2^n \geq \sum_{n=3}^k (2n+1) $$ for all $k$.

Base Case: $$ \sum_{n=3}^3 2^n \geq \sum_{n=3}^3 (2n+1). $$ Induction step: $$\begin{align} \sum_{n=3}^{k+1}2^n&=2^{k+1}+\sum_{n=3}^k2^n\\&\geq 2(k+1)+1+\sum_{n=3}^k(2n+1)\\&=\sum_{n=3}^{k+1}(2n+1). \end{align}$$

subrosar
  • 4,614