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!
On
The given equation is
$$ g_{n+2} - 6 g_{n+1} + 9 g_n = 3 \times 2^n + 7 \times 3^n $$
You can use the method of undetermined coefficients as follows. First determine the zeros of the the characteristic equation. They are $3, 3$. Hence, the proposed solution takes the form:
$g_n = A_1 (3)^n + A_2 n (3)^n + B_1 2^n + B_2 n^2 (3)^n $
The $A$-part is the homogenous part, while the $B$ part gives a particular solution.
Substituting the $B$ part into the equation, we get
$B_1 (2^{n+2} - 6 (2)^{n+1} + 9 (2)^n ) + B_2 ( (n+2)^2 3^{n+2} - 6 (n+1)^2 3^{n+1} + 9 n^2 3^n ) = 3 (2)^n + 7 (3)^n $
This simplifies to,
$B_1 (2)^n + B_2 (18) 3^n = 3 (2)^n + 7 (3)^n $
So $B_1 = 3 , B_2 = \dfrac{7}{18} $
Therefore, $g_n = A_1 (3)^n + A_2 n (3)^n + 3 (2)^n + \dfrac{7}{18} n^2 (3)^n $
Next we have to determine $A_1 $ and $A_2$ from the initial conditions.
$g_0 = 1 = A_1 + 3 $
So $A_1 = -2 $
And
$g_1 = 4 = (-2) (3) + A_2 (3) + 6 + \dfrac{7}{6} $
Hence, $A_2 = \dfrac{17}{18} $
Therefore, the complete expression for $g_n$ is
$g_n = -2 (3)^n + \dfrac{17}{18} n (3)^n + 3 (2)^n + \dfrac{7}{18} n^2 (3)^n$
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}$