Closed form solution to recurrence: $g(n)=(k-2)g(n-1)+(k-1)g(n-2)$ For the number of paths with exactly $n$ hops from one node to another in a $k$ node fully connected graph, we get the following recurrence:
$$g_n=(k-2)g_{n-1}+(k-1)g_{n-2}$$
With $g_1=1$, $g_0=0$ and $g_m=0 \;\; \forall \;\; m<0$.
Is there a way to get a closed form for this recurrence? For $k=3$, this yields the Jacobsthal numbers. 

For future reference, this recurrence represents the number of paths from one node to another in a $k$ node fully connected undirected graph and has the solution:
$$g(n) = \frac{(k-1)^n-(-1)^n}{(k)}$$

My attempt:
Let's try to construct the generating function.
$$B(x)=\sum\limits_{n=0}^\infty g_n x^n$$
We get:
$$B(x) = \sum\limits_{n=0}^\infty ((k-2)g_{n-1}+(k-1)g_{n-2})x^n$$
$$=>B(x) = (k-2)x\sum\limits_{n=0}^\infty g_{n-1}x^{n-1}+(k-1)x^2\sum\limits_{n=0}^\infty g_{n-2}x^{n-2}$$
$$=(k-2)x B(x)+(k-1)x^2 B(x)$$
But this just makes $B(x)$ cancel out and we don't get an expression for it.
 A: The issue is that your attempt to find the generating function doesn't actually make use of the initial conditions $g_0 = 0$, $g_1 = 1$ at all; you need to encode these somehow into the expression to actually get a useful result. (Also, the recurrence doesn't even hold for $g_1$, so we need to distinguish that case at the very least.) In particular, we can write
$$
B(x) = 0 \cdot x^0 + 1 \cdot x^1 + \sum_{n=2}^{\infty} ((k-2)g_{n-1} + (k-1)g_{n-2}) x^n.
$$
Can you take it from here?
Alternatively, instead of using generating functions, just construct the characteristic polynomial $\lambda^2 - (k-2) \lambda - (k-1) = 0$, which factorises as $(\lambda - (k-1))(\lambda + 1)=0$. So we can write the general form as
$$g_n = A\cdot (k-1)^n + B \cdot (-1)^n,$$
from which you can use your initial conditions to finish.
A: Let $g(n)=t^n$, then
$$t^2-(k-2)t-(k-1) \implies t=k-1,-1$$
Hence
$$g(n)=A (k-1)^n + B (-1)^n$$
The Proof 
Let $ax^2+bx+c=0$ has two roots $p,q$. then
$$ap^2+bp+c=0~~~(1), ~~aq^2+bq+c=0~~~(2)$$
Multiply (1) and (2) by $C_1 p^n$ and $C_2 q^n$ and add them
we get $$(a C_1 p^{n+2}+ C_2 q^{n+2}))+b (C_1 p^{n+1}+ C_2 q^{n+1})+ c(C_1 p^n + C_2 q^n)=0~~~~(3)$$
Define $$U_n=C_1 p^n+ C_2 q^n~~~~(4)$$
So (3) becomes
$$aU_{n+2}+bU_{n+1}+cU_n=0~~~~~~(5)$$
Hence the solution of (5) is given by (4).
