I am currently trying to solve a homogeneous recurrence relation of degree 8 that does only yield one characteristic root. I know that with degree 2 and only one root I can apply the formula below. I haven't been able to find any literature on larger equations though. $$ F(n) = a_1x_1^n + a_2nx_1^n $$
However, this formula doesn't apply to larger equations. The equation I am trying to solve is the following
$$ s(n) = 16s_{(n-1)}-112s_{(n-2)}+448s_{(n-3)}-1120s_{(n-4)}+1792s_{(n-5)}-1792s_{(n-6)}+1024s_{(n-7)}-256s_{(n-8)}, $$
The characteristic equation for this equation would be the following.
$$ r^8-16*1*r^{(8-1)}+112*1*r^{(8-2)}-448*1*r^{(8-3)}+1120*1*r^{(8-4)}-1792*1*r^{(8-5)}+1792*1*r^{(8-6)}-1024*1*r^{(8-7)}+256*1*r^{(8-8)} = 0 $$
Calculating r results in only one single solution.
$$ r = 2 $$
Now I obviously can't apply the formula I mentioned above to this. How do I write down the general solution for this equation now? I am having trouble understanding the next step. Could anyone point me in the right direction with an explanation of how to formulate the general equation that applies to bigger formulas or literature covering larger equations?
When you have multiple roots, say $a$ with multiplicity $m$, that means that your difference operator is a multiple of $(S-aI)^m$, where $S$ is the shift operator (Sx_n=x_{n+1}) and $I$ is the identity ($Ix_n=x_n$). In your case your equation is $(S-2I)^8s_{n}=0$.
When $a$ is a root you have that $(S-aI)a^n=a^{n+1}-a\cdot a^{n}=0$ and therefore $a^n$ is a solution of your homogeneous equation.
But for a larger exponent $(S-aI)^m$ you also have other solutions: $$(S-aI)^m(n^ka^n)=(S-aI)^{m-1}(Dn^k)a^n=...=(D^mn^{k})a^n$$ where $Dx_n=x_{n+1}-x_n$. When you take of a polynomial and apply $D$ to it, you get another polynomial with degree decreased by one. Therefore, for $k<m$ we get zero above.
This means that when $a$ is a roots of order $m$ of your characteristic polynomial then $n^ka^n$, for $k=0,1,...,m-1$ are solutions of your homogeneous equation, and they are linearly independent.
So, your general solution is a linear combination of $2^n,n2^n,...,n^{7}2^n$.