I have been working on a problem and have reached an impasse. I have a recurrence relation like this:
$n_{k} = 10n_{k-1} + 10^{k-1} - n_{k-2}$
with $n_{0} = 0$ and $n_{1} = 1$
I believe that it somehow pertains to the binomial distribution. Any tips to lead me towards a closed form solution? Is there a general way to 'brute force' a solution without knowing the form of the answer in advance?
Difference equations are similar to differential equations. In your case, you have an obvious particular solution of the equation: $n_{p,k}=10^{k+1}$. Then you have to look for solutions to the homogeneous equation $$ n_k-10n_{k-1}+n_{k-2}=0 $$ in the form of geometric sequence: $n_k=q^k$. When you try those, you get an equation for $q$ (the characteristic equation). In your case, you get two possible real values, hence two solutions $q_1^k$ and $q_2^k$ to your (homogeneous) equation. By linearity, the general solution of the homogeneous equation is $$ n_k=C_1q_1^k+C_2q_2^k $$ and then the general solution of the inhomogeneous one is $$ n_k=C_1q_1^k+C_2q_2^k+10^{k+1} $$ It only remains finding $C_1$ and $C_2$ using the initial conditions. You should end up with the solution given by Aleksas Domarkas.