Closed form solution to recurrence: $g(n)=(k-2)g(n-1)+(k-1)g(n-2)$

Question

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.

Answer 1

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.

Answer 2

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).