Solving the recurrence $a_{n+1} = k \cdot a_n - (k-1) \cdot a_{n-2}$ for $k \in \mathbb{N}$? I would like to solve the following recurrence for $k \in \mathbb{N}$ and $k > 1$:
$$a_{n+1} = k \cdot a_n - (k-1) \cdot a_{n-2},$$
with the base cases $a_1 = k, a_2 = k^2 - 1$ and $a_3 = k^3 - 2k + 1$.
I have plugged the recurrence relation into Mathematica and obtained an unwieldy expression, but I am interested in (a) whether there is a nicer formula and (b) how did Mathematica obtain what it obtained? Specifically, this is the solution it found (after some simplification):

 

I would also like to share how this recurrence came to be for some insight. I was thinking about the number of ways in which you could roll a $k$-faced dice $n$ times without getting two consecutive 1s. Then, I let $a_n$ denote the number of sequences of length $n$ without consecutive 1s and $b_n$ denote the number of sequences of length $n$ w/o consecutive 1s that ended with a 1. With some thinking, it is easy to see that this yields two recurrences: $a_{n+1} = (k - 1) \cdot b_n + k \cdot (a_n - b_n)$ and $b_{n+1} = a_{n} - b_{n}$. Then, with some tinkering, you'll note that the recurrence I wrote out above is the exact same $a$, just devoid of any references to $b$.
I would appreciate any input about the original recurrence, and the problem that motivated it :)
 A: From the first equation, we get:
$$ a_{n+1} = ka_n - b_n $$
which simplifies to
$$b_n = ka_n - a_{n+1}$$
Plugging this into $b_{n+1} = a_n - b_n$, I got:
$$a_{n+2} = (k-1) (a_n + a_{n+1})$$
This is consistent with a problem I've heard of before, which states that the number of coin flip sequences of length n without consecutive heads is the n'th fibonacci number. This should also be simpler since it only references the previous two terms.
Edit: This also suggests a simpler 'story' to get this recurrence relation: Either the last element is 1 or not. If it is, we have (k-1) choices for the second-to-last element, then an sequence of length n-2 with no consecutive 1's, it it's not, we have (k-1) choices for the last element and then a sequence of length n-1 with no consecutive 1's.
As comments mentioned, the way to solve linear recurrence relations with constant coefficients is pretty standard. One method it to use linear algebra to rewrite this as
$$ \begin{bmatrix} a_{n+1} \\ a_{n+2} \end{bmatrix} =  \begin{bmatrix} 0 & 1 \\ k-1 & k-1 \end{bmatrix} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$$
So
$$ \begin{bmatrix} a_{n} \\ a_{n+1} \end{bmatrix} =  \begin{bmatrix} 0 & 1 \\ k-1 & k-1 \end{bmatrix}^n \begin{bmatrix} 1 \\ k \end{bmatrix}$$
Where I chose 1 as $a_0$ and $k$ as $a_1$.
You would then use diagonalization to simplify this, which is conceptually easy but involves solving a quadratic, so the expression you end up with gets complicated. If you're interested in the details, I think there are a lot of resources online that show how you get the explicit formula for the fibobacci numbers, which should be very similar.
A: As Atreju noted, your recurrence can be simplified to $a_{n+2}=(k-1)(a_{n+1} + a_n)$. The standard method is to substitute powers of $x$ for successive iterations of $a$, giving the characteristic equation
$$x^2+(1-k)x+(1-k) =0$$
Then the values of $a$ are explicitly $a_n=cr_1^n + dr_2^n$, where $r_1, r_2$ are the roots of the characteristic equation, and $c,d$ depend on initial conditions. Then knowing $a_1=k, a_2=k^2+1$, you get the following system in $c,d$:
$$
\begin{cases}
k = c\left(\textstyle\frac12\displaystyle \left(k-1+\sqrt{(k-1)(k+3)}\right)\right) + d  \left(\textstyle\frac12\displaystyle \left(k-1-\sqrt{(k-1)(k+3)}\right)\right) \\
k^2+1 = c\left(\textstyle\frac12\displaystyle \left(k-1+\sqrt{(k-1)(k+3)}\right)\right)^2 + d  \left(\textstyle\frac12\displaystyle \left(k-1-\sqrt{(k-1)(k+3)}\right)\right)^2
\end{cases}
$$
The solution of which I'll leave to you, though WA gave you the solution in a weird form. The repeated $\sqrt{(k-1)(k+3)}$ from WA, and in that system, comes from a monic quadratic with $b=c=1-k \implies b^2-4ac=k^2-2k+1+4k-4=(k-1)(k+3)$
Despite all the square roots, it's perfectly possible that every value of $a_n$ produced by these will be an integer. (Edit: Note, for instance, that the Lucas numbers are explicitly $L_n=\phi^n + (1-\phi)^n$. Which is really pretty cool.)
