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 !
 A: This isn't really a recurrence relation.
Your "guess" is the right way to solve it. You can formalise your argument by reasoning that all internal points are the average of their neighbours - so only the straight line connecting the end-points can solve the relation. Note that this proves that your solution is correct, and unique.
A: Note that
$$
f(i)=\frac{f(i+1)+f(i-1)}{2}\implies f(i)-f(i-1)=f(i+1)-f(i)
$$
Thus, $f(i+1)-f(i)=a$ is a constant. Sum them up to get
$$
Ma=f(M)-f(0)=1
$$
Therefore, $a=\frac1M$.
A: 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.
A: 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.
