I would like to prove this inequality using induction
$$\sum_{k=1}^r \frac{2^k}{k^2} \le 9 \frac{2^r}{r^2}$$
The base case is simple enough: for $r=1$, we have:
Here's my attempt at the inductive case. Let $r=n$ and assuming the inequality is true for $r \le n-1$, then we have $$\frac{2^n}{n^2} + \sum_{k=1}^{n-1} \frac{2^k}{k^2} \le 9 \frac{2^{n-1}}{(n-1)^2} \frac{2(n-1)^2}{n^2}$$
But after simplifying this expression, and let $\sum_{k=1}^{n-1} \frac{2^k}{k^2} = 9 \frac{2^{n-1}}{(n-1)^2} = \alpha \ge 2$ by the inductive hypothesis, then we have: $$2^n \le \alpha n^2 - 4 \alpha n + 2 \alpha$$
where $n \ge 2$. But this inequality is false since a polynomial in n cannot grow faster than an exponential in n. So where did I go wrong?
In general, I have an inequality with a sum on one side and product on the other side, and I am not sure how to set up the inductive hypothesis in this case.
In the inductive step, you start with the $n-1$ case, and end some lines later with the $n$ case. Don't start with the $n$ case.
$$\frac{2^n}{n^2}+\sum_{k=1}^{n-1}\frac{2^k}{k^2}\leq\frac{2^n}{n^2}+9\frac{2^{n-1}}{(n-1)^2}\\ =\frac{9\times2^{n}}{n^2}\left(\frac{1}{9}+\frac{n^2}{2(n-1)^2}\right) $$
The final factor is eventually less than or equal to 1, so the inequality is true from then on.
You must check the first few cases of the whole sum separately before that factor becomes $\leq1$.