0

I have to prove the following inequation by induction

$$\sum_{k=2^{n+1}}^{2^{n+2}-1} a_k \leq 2^{n+1} \cdot a_{2^{n+1}}$$

but I have trouble with the inductive step when I have to choose $k = 2^{n+2}$. We also know that $ a_1 \geq a_2 \geq a_3 \geq ... \geq 0 $

Hans Hüttel
  • 4,271
Razmo
  • 47
  • Well that kinda straight forward since $a_{2^{n+1}} \geq a_k$ for all $k \geq 2^{n+1}$ by your assumption on the ordering of the $a_i$'s. Also the sum contains $2^{n+1}$ elements, hence the factor in front of $a_{2^{n+1}}$. – Zubzub Jun 05 '17 at 14:21
  • Well i wrote that both sides have an equal numer of addends. While the addends on the left side gets less and less, the addends on the right side stay the same. The first addend on both sides are equals. Is this correct? – Razmo Jun 05 '17 at 14:56

1 Answers1

1

Induction on $n$ doesn't work for this problem. Rather, it is the observation that if $A = \{a_1, \dots, a_m\}$ and $a_1 = \max A$ then $\sum A \le m a_1$. That is, each term in the sum is less than or equal to $a_1$ and therefore

$$ \sum A = \sum_{i = 1}^m a_i \le \sum_{i = 1}^m a_1 = m a_1. $$

You can prove this formally by induction on $m$ if you want:

$$ a_m + \sum_{i = 1}^{m - 1} a_i \le a_m + (m - 1)a_1 \le a_1 + (m - 1)a_1 = ma_1. $$

Trevor Gunn
  • 27,041