Combinatorics Recurrence relation

Question

Let $h_n$ be a number sequence where $h_n = 3h_{n-1} - 2h_{n-2}$ with $h_0 = 0$ and $h_1 = 1$. Compute the ordinary generating function of $h_n$ and then using the generating function compute a formula for $h_n$.

Does this start looks right? We write the recurrence relation in form: $$h_n - 3h_{(n-1)} + 2h_{(n-2)} = 0$$

Let $g(x) = h_0 + h_1 x + h_2 x^2+\ldots$ be the generating function for sequence $h_0, h_1,\ldots$.

We have $g(x) = h_0 + h_1 x + \ldots$ as well as $-3x\,g(x) = -3h_0 x -3 h_1 x^2 - \ldots$ and $2x^2\,g(x) = 2h_0 x^2 + 2h_1 x^3 +\ldots$.

Adding all three would give us :

$$(1 -3x + 2x^2) g(x) = h_0 + (-3h_0 + h_1) x + (2h_0 -3h_1 + h_2) x^2 + \ldots + (h_n -3h_{n-1} + h_{n-2}) x^n + \ldots$$

Since $h_n - 3h_{n-1} + 2 h_{n-2} = 0$ and since $h_0 = 0, h_1 = 1$.

So we know that $(1 - 3x + 2x^2) g(x)= 1 + x$ and that leads to:

$$ g(x) = \frac{1+x}{(1-2x)(1-x)}.$$

Does this look like a correct start?

Answer 1

Once you have: $$ g(x)=\sum_{n\geq 0}h_n x^n = \frac{\color{red}{x}}{(1-2x)(1-x)} = \frac{1}{1-2x}-\frac{1}{1-x}\tag{1}$$ it is straightfoward to check that $\color{red}{h_n=2^n-1}.$

Just check your computations since the value in zero of $\frac{1+x}{(1-2x)(1-x)}$ is one, while you have $h_0=0$.

Answer 2

It is fine. Now you need to split this expression $g(x)=\frac{1+x}{(1-2x)(1-x)}$ as a combination of simple elements, i.e. terms of the form $\frac{1}{a x + b}$ (in your case). From there, finishing should be easy. You may also check your answer by directly computing the terms $h_n$ as $A \lambda^n + B \mu^n$ for the characteristic roots $\lambda$ and $\mu$.