Help me evaluate this infinite sum I have the following problem:
For any positive integer n, let $\langle n \rangle$ denote the integer nearest to $\sqrt n$.
(a) Given a positive integer $k$, describe all positive integers $n$ such that $\langle n \rangle = k$.
(b) Show that $$\sum_{n=1}^\infty{\frac{2^{\langle n \rangle}+2^{-\langle n \rangle}}{2^n}}=3$$
My progress: The first one is rather easy. As $$\left( k-\frac{1}{2} \right) < \sqrt n < \left( k+\frac{1}{2} \right) \implies \left( k-\frac{1}{2} \right)^2 < n < \left( k+\frac{1}{2} \right)^2 \implies \left( k^2-k+1 \right) \leq n \leq \left( k^2+k \right)$$
Actually, there would be $2k$ such integers.
But, I have no idea how to approach the second problem. Please give me some hints. 
 A: The idea is to rewrite the sum as a double sum by observing that $$\langle m^2 + k \rangle = m$$ for $k \in \{-m+1, \ldots, m\}$.  Therefore, $$\begin{align*} S &= \sum_{n=1}^\infty \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n} \\ &= \sum_{m=1}^\infty \sum_{k=-m+1}^{m} \frac{2^m + 2^{-m}}{2^{m^2+k}} \\ &= \sum_{m=1}^\infty \frac{2^m + 2^{-m}}{2^{m^2}} \sum_{k=-m+1}^m \frac{1}{2^k} \\ &= \sum_{m=1}^\infty \frac{2^m + 2^{-m}}{2^{m^2}} \left(2^m - 2^{-m}\right) \\ &= \sum_{m=1}^\infty \frac{2^{2m} - 2^{-2m}}{2^{m^2}} \\ &= \sum_{m=1}^\infty 2^{-m(m-2)} - 2^{-m(m+2)} \\ &= \sum_{m=1}^\infty 2^{-m(m-2)} - \sum_{k=3}^\infty 2^{-(k-2)k} \\ &= \sum_{m=1}^2 2^{-m(m-2)} = 2^1 + 2^0 = 3.\end{align*}$$ 
A: Direct computation seems to work. I recall this problem being an old Putnam problem.
We have $\langle n \rangle = k$, iff $n \in [k^2 - k + 1, k^2 + k]$. 
Now, let's compute this sum.
$$
\sum_{n = 1}^\infty \frac{2^{\langle n \rangle} + 2^{-\langle n \rangle}}{2^n}
= \sum_{k=1}^\infty \sum_{i=k^2 - k + 1}^{k^2 + k} \frac{2^k + 2^{-k}}{2^i} 
= \sum_{k=1}^\infty \frac{2^{2k}+1}{2^k}\sum_{i=k^2 - k + 1}^{k^2 + k} \frac1{2^i} 
= \sum_{k=1}^\infty \frac{2^{2k}+1}{2^{k^2+1}}\sum_{i=0}^{2k-1} \frac{1}{2^i} 
= \sum_{k=1}^\infty \frac{2^{2k}+1}{2^{k^2 + 1}}\frac{1 - \frac{1}{4^k}}{1-\frac{1}{2}} 
= \sum_{k=1}^\infty \frac{2^{2k}+1}{2^{k^2 + 1}}\frac{2^{2k}-1}{2^{2k-1}} 
= \sum_{k=1}^\infty \frac{2^{4k}-1}{2^{k^2 + 2k}} 
= \sum_{k=1}^\infty \left(2^{1-(k-1)^2} - 2^{1-(k+1)^2}\right) 
= 2^1 + 2^0 = 3$$
