Solving non-homogeneous recurrence relations [closed]

Find $g_{n}$ if $g_{n+2}-6g_{n+1}+9g_{n}=3\times 2^n + 7\times (3)^n$ given $g_{0}=1,g_{1}=4$.

How can I proceed to solve these kind of recurrence relations? I cannot show any work since I haven't made any progress. I was thinking of trying out values and then guessing a formula, and then inducting on it. I also know generating functions, but I can't understand how to use them here.

Any help is appreciated!

The general solution for this kind of recurrence problems is through "generating function" method which can be described as follow.

Assume there is an analytic function $f(x)$ with the power series expansion $f(x) = \sum_{n=0}^{\infty}g_nx^n$. Now we rewrite it as

$$f(x) = g_0+g_1x+\sum_{n=2}^{\infty}g_nx^n = 1 + 4x + \sum_{n=0}^{\infty}g_{n+2}x^{n+2}$$

Now using our main equation $g_{n+2}-6g_{n+1}+9g_{n}=3\times 2^n + 7\times (3)^n$ we get $g_{n+2}=6g_{n+1}-9g_{n}+3\times 2^n + 7\times (3)^n$ and we substitute in the above expression

$$f(x) = 1 + 4x + 6\sum_{n=0}^{\infty}g_{n+1}x^{n+2}-9\sum_{n=0}^{\infty}g_{n}x^{n+2} + 3x^2\sum_{n=0}^{\infty}(2x)^n + 7x^2\sum_{n=0}^{\infty}(3x)^n$$

Now assuming $\{|2x|<1\}\cap \{|3x|<1\}$ in other words the series above be convergent, we can simplify it as follow (using geometric series formula)

$$f(x) = 1+4x+6x\sum_{n=0}^{\infty}g_{n+1}x^{n+1}-9x^2\sum_{n=0}^{\infty}g_{n}x^{n}+\frac{3x^2}{1-2x} + \frac{7x^2}{1-3x}\\ =1+4x+6x(f(x)-1) - 9x^2f(x)+\frac{3x^2}{1-2x} + \frac{7x^2}{1-3x}$$

please notice that $6x\sum_{n=0}^{\infty}g_{n+1}x^{n+1}$ is simplified as $6x\sum_{n=0}^{\infty}g_{n+1}x^{n+1} = 6x\sum_{n=1}^{\infty}g_{n}x^{n} = 6x(\sum_{n=1}^{\infty}g_{n}x^{n}+g_0-g_0)\\ = 6x(\sum_{n=0}^{\infty}g_{n}x^{n}-g_0)=6x(f(x)-1)$.

Now we have an equation in terms of $f(x)$ which can be solved as follow

$$f(x) = f(x)(6x-9x^2) + \left(1 + 4x - 6x + \frac{3x^2}{1-2x} + \frac{7x^2}{1-3x}\right) \\ \Rightarrow f(x)(1-6x+9x^2) = 1-2x + \frac{3x^2}{1-2x} + \frac{7x^2}{1-3x} \\ \Rightarrow f(x) = \frac{1-2x}{(1-3x)^2} + \frac{3x^2}{(1-2x)(1-3x)^2} + \frac{7x^2}{(1-3x)^3}$$

So we found the generating function $f(x), |x|\le \frac{1}{3}$, now we have to find the power series representation of $f(x)$ to find the original sequence $g_n$. We use partial fraction expansion:

$$f(x) = \frac{3}{1-2x} + \frac{-\frac{10}{9}}{1-3x} + \frac{-\frac{2}{9}}{(1-3x)^2} + \frac{\frac{7}{9}}{(1-3x)^3}$$

I believe you can do the rest using geometric series and derivative.

Hint: $\sum_{n=0}^{\infty}x^n = \frac{1}{1-x} \overset{\frac{d}{dx}}{\Rightarrow} \sum_{n=0}^{\infty}nx^n = \frac{x}{(1-x)^2}$