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.

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.
