$a_{m+n}+a_{m-n}=\frac{1}{2}(a_{2m}+a_{2n}), a_1=1$, find $ a_{1995}$ 
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.


*

*$n=0$ gives $a_{2m}=4a_{m}$

*$m=n=0$ gives $a_{0}=0$

*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$

*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})$?
 A: 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$.
A: 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$.
