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 !

One good method is to use generating functions.
First let's extend the sequence $f(i)$ by defining it not just for $0 \le i \le M$, but for al $i \ge 0$.  (You can see that the recurrence relation allows this extension by solving for $f(i+1)$.)  Then, if we write
$$
F(x) = \sum_{i = 0}^\infty f(i) x^i
$$
the recurrence $f(i) = \frac{f(i-1) + f(i+1)}{2}$ becomes
$$
F(x) = \frac12 \left( x + \frac1x \right) F(x) - \frac{f(0)}{2x} - \frac{f(1)}{2} + f(0)
$$
Since $f(0) = 0$, the above becomes
$$
2xF(x) = \left(x^2 + 1\right) F(x) - f(1)x
$$
So solving, we get
$$
F(x) = \frac{f(1)x}{(1-x)^2} = f(1) \left( x + 2x^2 + 3x^3 + 4x^4 + \cdots \right)
$$
Hence $f(i) = i \cdot f(1)$ for all $i$.  Since $f(M) = 1$, we get that $f(1) = \frac1M$, hence $f(i) = \frac{i}{M}$ as desired.
