Solving a recurrence equation with constant term so I have this recurrence equation:
$$G(n) = 2G(n-1) + 100 $$
I believe this a linear non-homogeneous equation of the form $G(n) = LH + F(n) $ where LH is the associated linear homogeneous equation which is G(n-1).
If $F(n)$ is $2n$ we can take a trial solution as $Cn+D$ and solve or if F(n) is say $7^n$ we can take $C\cdot7^n$ and try to solve for constants $C$ and $D$. What do I do if $F(n)$ is a constant like $100$. The initial condition is G($0$) = $2$. 
How do I go about solving this? 
Thanks in advance!
 A: You can subtract recurrences against shifted forms of themselves to drop out the constant term.
$G(n) = 2G(n-1) + 100$
$G(n-1) = 2G(n-2) + 100$
Subtract:
$G(n) - G(n-1) = 2G(n-1) - 2G(n-2)$
Rearrange:
$G(n)  = 3G(n-1) - 2G(n-2)$
Now it's just a regular homogeneous linear recurrence requiring initial terms $G(0) = 2$ and $G(1) = 104$. By removing the constant term from the recurrence we've taken it back into account in the initial conditions since we increased the degree.
The characteristic polynomial is $x^2-3x+2 = 0$ which has roots $x=2$ and $x=1$, implying that $G(n) = \alpha \cdot 2^n + \beta \cdot 1^n$.
$G(0) = 2 = \alpha \cdot 2^0 + \beta \cdot 1^0 = \alpha + \beta$
$G(1) = 104 = \alpha \cdot 2^1 + \beta \cdot 1^1 = 2\alpha + \beta$
This simplifies to $\alpha = 102$ and $\beta = -100$, so $G(n) = 102 \cdot 2^n - 100 \cdot 1^n = 102 \cdot 2^n - 100$
A: Another approach using generating functions:
$\begin{align}
F(x) &= \sum_{n=0}^{\infty} G(n) x^n \\
F(x) &= 2x^0 + \sum_{n=1}^{\infty} (2G(n-1) + 100) x^n \\
F(x) &= 2 + 2\sum_{n=1}^{\infty} G(n-1)x^n + 100\sum_{n=1}^{\infty}  x^n \\
F(x) &= 2 + 2x\sum_{n=1}^{\infty} G(n-1)x^{n-1} + 100(-x^0 + \sum_{n=0}^{\infty}  x^n) \\
F(x) &= 2 + 2x\sum_{n=0}^{\infty} G(n)x^{n} + 100(-1 + \sum_{n=0}^{\infty}  x^n) \\
F(x) &= 2 + 2xF(x) + 100\left(-1 + \frac{1}{1-x}\right) \\
F(x) &= 102 \cdot \frac{1}{1 - 2 x}  - 100 \cdot \frac{1}{1 - x}\\
\end{align}$
Take the $n$th coefficient of this generating function and we get:
$G(n) = 102 \cdot 2^n  - 100$
A: Repeatedly apply the rule $G(n) = 2G(n - 1) + 100$:
\begin{align}
G(n) &= 2G(n - 1) + 1 \cdot 100 \\
&= 2\big( 2G(n - 2) + 100 \big) + 1 \cdot 100 \\
&= 4G(n - 2) + (2 + 1) \cdot 100 \\
&= 4\big( 2G(n - 3) + 100 \big) + (2 + 1) \cdot 100 \\
&= 8G(n - 3) + (4 + 2 + 1) \cdot 100
\end{align}
You should see the following pattern (try proving it by induction):
$$ G(n) = 2^{\color{blue}k}G(n - \color{blue}k) + (2^{\color{blue}k - 1} + \dots + 2^1 + 2^0) \cdot 100 = 2^kG(n-k)+ (2^k - 1)100. $$
Thus
$$ G(n) = 2^{\color{blue}n}G(n - \color{blue}n) + (2^{\color{blue}n} - 1) \cdot 100 = 2^nG(0) + (2^n - 1) \cdot 100. $$
A: Any sequence of the form
$$f_n=Af_{n-1}+B$$
can be expressed as a generalized Fibonacci sequence
$$f_n=af_{n-1}+bf_{n-2}$$
where $a=A+1$ and $b=-A$, by incrementing the original sequence and subtracting to eliminate $B$. Once this is done we can develop a general solution for $f_n$ in terms of $A,B,f_0$ as described below.
There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas,  and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)
We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that
$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{af_0}{2} \frac{\alpha^n+\beta^n}{\alpha+\beta}=\frac{(f_1-f_0\beta)\alpha^n-(f_1-f_0\alpha)\beta^n}{\alpha-\beta}$$
where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$. This can also be expressed in various other forms.
Now, specializing to the sequence $f_n=Af_{n-1}+B$, we find the general solution for all such sequences that $\alpha=A$, $\beta=1$ and
$$f_n=\frac{[(A-1)f_0+B)A^n-B}{A-1}$$
This solution has been tested numerically against the original sequence for randomly chosen $A,B,f_0\in[-3,3]$ and is in perfect agreement.
In your case, with $A=2,~B=100$ we have
$$G(n)=102\cdot 2^n-100$$
as already seen in other answers. However, now you have the solution for all such problems.
