1

$$\forall{n,a>1}:\;\sum\limits_{k=1}^{2^n-1}\frac{1}{k^a}\;\leq\left(\frac{1-2^{n(1-a)}}{1-2^{1-a}}\right)$$

For any fixed value of $a > 1$.

Induction step:

$$\sum_{k=1}^{2^{n+1} - 1} \frac{1}{k^a} = (\sum\limits_{k=1}^{2^n-1}\frac{1}{k^a}) + \frac{1}{(2^n)^a} + \frac{1}{(2^n + 1)^a} + \frac{1}{(2^n + 2)^a} + ... + \frac{1}{(2^{n+1} -1)^a} \leq\left(\frac{1-2^{n(1-a)}}{1-2^{1-a}}\right) + \frac{1}{(2^n)^a} + \frac{1}{(2^n + 1)^a} + \frac{1}{(2^n + 2)^a} + ... + \frac{1}{(2^{n+1} -1)^a}$$

I need help from Induction step and on. So if someone would help me, that would be greatly appreciated! People on this website keep putting this problem on hold even though I have clarified it as much as I can.

I need to prove P(n+1) is true:

$$\forall{n,a>1}:\;\sum\limits_{k=1}^{2^{n+1}-1}\frac{1}{k^a}\;\leq\left(\frac{1-2^{(n+1)(1-a)}}{1-2^{1-a}}\right)$$

user181415
  • 39
  • 7
  • Hint: $$\frac{1}{(2^n)^a} + \frac{1}{(2^n + 1)^a} + \ldots + \frac{1}{(2^{n+1} - 1)^a} \leq 2^n \cdot \frac{1}{(2^n)^a}$$ – Pedro M. Oct 07 '14 at 23:15
  • Pedro, would you be able to write an answer? Because I already tried that and I wasn't able to prove this. – user181415 Oct 07 '14 at 23:18

2 Answers2

0

Hint. $$\sum\limits_{k=2^n}^{2^{n+1}-1} \frac{1}{k^a} \leq \sum\limits_{k=2^n}^{2^{n+1}-1}\frac{1}{2^{na}}=\frac{1}{2^{n(a-1)}}$$ and $$ \frac{1 - 2^{n(1-a)}}{1-2^{1-a}} + \frac{1}{2^{n(a-1)}} = \cdots $$ By the way, a circuitous route might by using the geometric series formula (you certainly don't need to do this, but it's interesting), you know that $$ \sum\limits_{k=0}^{n-1} \frac{1}{2^{k(a-1)}} = \frac{1-2^{n(1-a)}}{1-2^{1-a}} $$ and so $$ \frac{1 - 2^{n(1-a)}}{1-2^{1-a}} + \frac{1}{2^{n(a-1)}} = \sum\limits_{k=0}^{n-1} \frac{1}{2^{k(a-1)}} + \frac{1}{2^{n(a-1)}} = \sum\limits_{k=0}^n \frac{1}{2^{k(a-1)}} = \cdots $$

Tom
  • 9,978
0

Ellaborating on the hint:

Notice that $$\frac{1 - 2^{n(1-a)}}{1 - 2^{1-a}} = 1 + 2^{1-a} + \ldots + 2^{(n-1)(1-a)}$$ and that $$\frac{1}{(2^n)^a} + \frac{1}{(2^n + 1)^a} + \ldots + \frac{1}{(2^{n+1} - 1)^a} \leq 2^n \cdot \frac{1}{(2^n)^a}.$$

Now $$\sum_{k=1}^{2^{n+1}-1}\frac{1}{k^a} = \sum_{k=1}^{2^{n}-1}\frac{1}{k^a} + \sum_{k=2^n}^{2^{n+1}-1}\frac{1}{k^a}$$ By the induction hypothesis,
\begin{align*} \sum_{k=1}^{2^{n+1}-1}\frac{1}{k^a} &\leq \frac{1 - 2^{n(1-a)}}{1 - 2^{1-a}} + \sum_{k=2^n}^{2^{n+1}-1}\frac{1}{k^a} \\ &\leq 1 + 2^{1-a} + \ldots + 2^{(n-1)(1-a)} + 2^{n(1-a)}. \end{align*} Now what does this final expression evaluate to? It is the sum of a certain geometric progression.

Pedro M.
  • 3,061
  • 18
  • 19
  • are you talking about the expression I wrote in my post? – user181415 Oct 07 '14 at 23:55
  • Like this is what I should end up with once I do some algebra, correct? Because I am trying to prove this is true which is part of n+1. $$\left(\frac{1-2^{(n+1)(1-a)}}{1-2^{1-a}}\right)$$ – user181415 Oct 07 '14 at 23:59
  • Do you know how to calculate the sum of a geometric progression? – Pedro M. Oct 08 '14 at 01:04
  • Then I believe you need to study up on that before tackling this problem, since it is clearly a requirement. Wikipedia is a good place to start. – Pedro M. Oct 08 '14 at 01:09
  • well I know how to basic geometric progression calculations but I don't understand how to use that here. – user181415 Oct 08 '14 at 01:11
  • Yes it does. But again, if you cannot work this out yourself, you really need to study that wikipedia link. – Pedro M. Oct 08 '14 at 01:31
  • wait so I just write that the last expression you wrote is equal to what I wrote in the comments above? Or is there some algebra involved to evaluate that geometric progression? – user181415 Oct 08 '14 at 01:37
  • Like is there a step between that last expression and what it evaluates to(which is what I have written in parentheses in a comment above) that involves some algebra? – user181415 Oct 08 '14 at 01:47
  • Please note that, while we strive to help as much as we can, we don't provide complete answers to homework problems. Regarding your question, this is something to be answered by your teacher (according to his/her goal in this specific problem). – Pedro M. Oct 08 '14 at 01:59