Closed form solution to simple recurrence

Question

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 !

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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