Context: This question arises from https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf (specifically problem 26 on page 427). The problem asks one to prove that a proffered equation (i.e., $f_k\!=\!k(n-k)$) is indeed a solution to the finite difference equation defined on a $n$ interval 1-dimensional line: $$ f_k=\frac{1}{2}f_{k-1}+\frac{1}{2}f_{k+1}+1, $$ with boundary conditions of $f_0\!=\!f_n\!=\!0$.
Question: While I understand the proof showing that $f_k\!=\!k(n-k)$ is a solution to this equation, what is not so clear to me is how $k(n-k)$ was derived in the first place. Without knowing a priori that $k(n-k)$ is the solution, how would one go about solving such a difference equation?
You can sometimes solve these types of problems by assuming a solution of a particular form and determining the values of the parameters which would solve the equation (compare with the method of undetermined coefficients used to solve ODE's). With experience you can sometimes tell from the structure of the equation what type of Ansatz would be appropriate.
Lets try an Ansatz which is a polynomial in $k$.
$$ f_k = A + B k + C k^2,$$
the boundary conditions give us equations for $A$, $B$, and $C$. First consider $f_0=0$.
$$ f_0 = 0 $$
$$ A = 0 $$
Now we have $f_k = Bk + Ck^2$. Now lets appliy the boundary condition $f_n = 0 $.
$$ f_n = 0 $$ $$ B n + C n^2 = 0 $$
$$ B + C n = 0 $$
$$ B = - C n $$
Now we have $ f_k = - Cn k + Ck^2$ which can be written as,
$$ f_k = C k (k-n).$$
All that is left is to determine $C$. We will use the finite difference equation,
$$ f_k = \frac12 f_{k-1} + \frac12 f_{k+1} + 1$$
$$ C k (k-n) = \frac12 C (k-1) (k-1-n) + \frac12 C (k+1) (k+1-n) + 1$$
$$ C k^2 - Ckn = \frac12 C \Big(k^2 - (n+2)k +(1+n) \Big) + \frac12 C \Big(k^2 + (2-n)k + (1-n) \Big) + 1$$
$$ C k^2 - Ckn = \frac12 C \Big(2k^2 - (2n)k +2 \Big) + 1$$
$$ C k^2 - Ckn = Ck^2 - Cnk +C + 1$$
$$0 = C + 1$$
$$C=-1$$
We now have our solution,
$$ f_k = k(n-k)$$
For comparison consider $f_{k} = f_{k+1} - f_{k-1}$. If we apply the Ansatz $f_k = e^{\lambda k}$ we get the following,
$$ e^{\lambda k } = e^{\lambda(k+1)} - e^{\lambda(k-1)} ,$$
$$ e^{\lambda k } =e^{\lambda k}\Big( e^{\lambda} - e^{-\lambda}\Big), $$ $$ 1=\Big( e^{\lambda} - e^{-\lambda}\Big), $$ $$ 1=2 \sinh(\lambda), $$
from experience I know that if the relationship only involves $f_{k+j}$ for various $j$ then an exponential Ansatz is the way to go.
Why would we use a polynomial Ansatz for your problem? Because there is a constant term. Notice that $(k+j)^n = k^n + n k^{n-1} + \cdots j^n$ always has a term in the sum which is independent of $k$. When I see the "1" in your equation,
$$ f_k = \frac12 f_{k+1} + \frac12 f_{k-1} + \color{red}1 ,$$
I figure there is going to be a polynomial solution.
We can also rearrange your recurrence relation to look like.
$$ 0 = \color{blue} { \frac{ f_{k+1} - 2 f_{k} + f_{k-1} }{2} } + 1 $$
The blue fraction looks like the finite difference formula for the second derivative. This would lead me to think that the solution to the discrete problem is related to the solution to the differential equation,
$$ 0 = f''(x) + 1 \Rightarrow f(x) = -x^2 + Bx + C,$$
this is another reason to assume a quadratic polynomial for $f_k$.