<s>[INST] Inductive proof of inequality involving summation and nested exponents What is the best way to approach this problem?
$$\sum_{k=1}^{n} \frac{1}{2^{k^2}} \leq 
1-\frac{1}{2^{n^2}}$$
So far I have proved this works for a base case where $n=1$
$$\sum_{k=1}^{1} \frac{1}{2^{k^2}} \leq 
1-\frac{1}{2^{1^2}}$$
$$\frac{1}{2} \leq \frac{1}{2}$$
Now I have the first part of the inductive case where $n=m$
$$\sum_{k=1}^{m} \frac{1}{2^{k^2}} \leq 
1-\frac{1}{2^{m^2}}$$
This is the point where I am stuck.
How can the expression above be rearranged to prove that
$$\sum_{k=1}^{m+1} \frac{1}{2^{k^2}} \leq 
1-\frac{1}{2^{(m+1)^2}}$$
and therefore complete the inductive case?
 [/INST] You have the inductive case of $n = m$ giving
$$\sum_{k=1}^{m} \frac{1}{2^{k^2}} \leq 1-\frac{1}{2^{m^2}} \tag{1}\label{eq1A}$$
A common method to use induction with inequalities is to go from the inductive case, given above, to the case you're trying to prove, i.e., for $n = m + 1$, by changing the values so one side is true and then showing the other side is still true as well. In this case, the change is simplest to deal with on the left side as it just involves adding $\dfrac{1}{2^{(m+1)^2}}$. Thus, adding this value to both sides gives
$$\begin{equation}\begin{aligned}
\sum_{k=1}^{m+1} \frac{1}{2^{k^2}} & \leq 1 - \frac{1}{2^{m^2}} + \frac{1}{2^{(m+1)^2}} \\
& = 1 - \frac{1}{2^{(m+1)^2}} + \left(\frac{1}{2^{(m+1)^2}} - \frac{1}{2^{m^2}} + \frac{1}{2^{(m+1)^2}}\right) \\
& = 1 - \frac{1}{2^{(m+1)^2}} + \left(\frac{2}{2^{(m+1)^2}} - \frac{1}{2^{m^2}}\right) \\
& = 1 - \frac{1}{2^{(m+1)^2}} + \left(\frac{1}{2^{(m+1)^2 - 1}} - \frac{1}{2^{m^2}}\right) \\
& \lt 1 - \frac{1}{2^{(m+1)^2}}
\end{aligned}\end{equation}\tag{2}\label{eq2A}$$
Going to the last line can be done since $(m+1)^2 - 1 = m^2 + 2m \gt m^2$, so you have
$$\frac{1}{2^{(m+1)^2 - 1}} \lt \frac{1}{2^{m^2}} \implies \frac{1}{2^{(m+1)^2 - 1}} - \frac{1}{2^{m^2}} \lt 0 \tag{3}\label{eq3A}$$
This shows the problem you're trying to solve for is true for $n = m + 1$, thus completing the inductive process. You can now conclude that
$$\sum_{k=1}^{n} \frac{1}{2^{k^2}} \leq 1-\frac{1}{2^{n^2}} \tag{4}\label{eq4A}$$
is true for all integers $n \ge 1$.
</s>