$a_{m+n}+a_{m-n}=\frac{1}{2}(a_{2m}+a_{2n}), a_1=1$, find $ a_{1995}$

Question

The sequence $a_0,a_1,a_2,...$ satisfies $a_{m+n}+a_{m-n}=\frac{1}{2}(a_{2m}+a_{2n}), a_1=1$ for all non-negative integers $m,n$ with $m\ge n$. Find $a_{1995}$

This is a quick sketch of my solution.

1. $n=0$ gives $a_{2m}=4a_{m}$

2. $m=n=0$ gives $a_{0}=0$

3. Plugging $a_{2m}=4a_{m},a_{2n}=4a_{n}$ (with $n=1$) back to the question gives $a_{m+1}=2a_{m}-a_{m-1}+2$

4. Trying small values led me to conjecture that $a_n=n^2$

My question is a a lot simpler: My book's solution also conjecture that $a_n=n^2$, and proves it by strong induction. Can't I just check to see if it satisfy $a_1=1$ and $a_{m+n}+a_{m-n}=\frac{1}{2}(a_{2m}+a_{2n})$?

Answer 1

You can readily check that $a_n=n^2$ satisfies the given condition: $1^2=1$ and $(m+n)^2+(m-n)^2=\frac12((2m)^2+(2n)^2)$. So far, so good. Now you know that this is one of possibly many solutions. In order to conclude that this is the only solution, you have to do a bit more. Fortunately, you already obtained a recursion in your third point, where you express $a_{m+1}$ in terms of $a_m$ and $a_{m-1}$. As a consequence, the sequence is uniquely determined by $a_0$ and $a_1$. Of these, we are already given that $a_1=1$. This would still allow for many different solution if you hadn't already established that necessarily $a_0=0$.

Answer 2

I found this solution:

\begin{align} a_{m+1}&=2a_{m}-a_{m-1}+2\\ a_{m}&=2a_{m-1}-a_{m-2}+2\\ &\vdots\\ a_{3}&=2a_{2}-a_{1}+2\\ a_{2}&=2a_{1}-a_{0}+2\\ \end{align}

Sum both sides to get:

\begin{align} a_{m+1}&=2a_{m}+2m+1. \end{align}

Then given $a_0=0$ and $a_1=1$, I tried to see the pattern of last equation and got (for $m\geq2$)

\begin{align} a_{m+1}&=\sum_{i=0}^m2^i+2m\sum_{i=0}^{m-1}2^i-\sum_{i=0}^{m-2}(i+1)2^{i+2}\quad. \end{align}

---

Not 100% sure if it is true, just trying to get $a_{m+1}$ in terms of $m$.