Closed form solution to simple recurrence I have this recurrence :
$$f(i) = \begin{cases}
0 &i=0\\
1 &i=M\\
\frac{f(i-1) + f(i+1)} 2& 0 < i < M
\end{cases}$$
I have guessed that
$$f(i) = \frac i M$$
and proved it via induction.
What is the right way of solving it without guessing ? 
Later Edit:
Thank you very much for your answers. I found them all very helpful. 
Thank you very much for your time !

If you look at the third form, you should recognize it as an arithmetic mean. $f(i)$ is the mean of $f(i-1)$ and $f(i+1)$, which tells you immediately that you're looking for a linear equation. The endpoints then give you slope and intercept.
