difference of recursive equations Lets have two recursive equations:
\begin{align}
f(0) &= 2  \\
f(n+1) &= 3 \cdot f(n) +  8 \cdot n \\ \\
g(0) &= -2 \\
g(n+1) &= 3 \cdot  g(n) + 12
\end{align}
We want a explicit equation for f(x) - g (x).
I firstly tried to do in manually for first $n$ numbers
\begin{array}{|c|c|c|c|}
\hline
n & f(n) & g(n) & f(n) - g(n) \\ \hline
0 & 2 & -2 &    4 \\ \hline
1 & 6  & 6 &    0 \\ \hline
2 & 26  & 30 &  -4 \\ \hline
3 & 94 & 102 &  -8 \\ \hline
4 & 306  & 318 & -12 \\ \hline
\end{array}
We can deduce that $f(n) - g(n) = 4 - 4n$
But now we have to prove it.
Lets extend recursive equation $f(n)$:
$$f(n) = 3^n \cdot f(0) + 8 \cdot (3^{n+1} \cdot 0 + \dots + 3^{0}(n-1))$$
for $g$ we get $$g(n) = 3^n \cdot g(0) + 12 \cdot (3^{n-1} + \dots + 3^0)$$
We can simply check this by induction but I will skip it, so the question won't be so long.
Now lets  put it together:
$$
f(n) - g(n) = 2 \cdot 3^n + 8 * 3^{n-1} \cdot 0 + ... + 3^0 \cdot (n-1) + 2 \cdot 3^n - 4 \cdot 3 \cdot ( 3^{n-1}+ ... + 3^0)= \\
= 4 \cdot 3^n  + 8 \cdot (3^{n-1} \cdot 0 + ... + 3^0(n-1)) - 4 \cdot (3^n + 3^{n-1} + ... + 3^1) = \\
= 8 \cdot (3^{n-1} \cdot 0 + ... + 3^0(n-1)) - 4 \cdot (3^{n-1} + ... + 3^1 + 3^0) + 4 \cdot 3^0 = \\
= 8 \cdot (3^{n-1} \cdot 0 + ... + 3^0(n-1)) - 4 \cdot (3^{n-1} + ... + 3^1 + 3^0) + 4
$$
As we can see, we already got the $4$, so to get $-4n + 4$, the rest of the equation must equal $-4n$. But this is where I don't know how to continue.
How to prove that:
$$8 \cdot (3^{n-1} \cdot 0 + \dots + 3^0(n-1)) - 4 \cdot (3^{n-1} + \dots + 3^1 + 3^0) = -4n$$
All I could do is this:
\begin{align}
&8 \cdot (3^{n-1} \cdot 0 + \dots + 3^0(n-1)) - 4 \cdot (3^{n-1} + \dots + 3^1 + 3^0) = \\
&= 4 \cdot (\frac{0}{2}3^{n-1} + \dots + \frac{1}{2} \cdot (n-1) - 4 * (\frac{2}{2}3^{n-1} + \dots + \frac{2}{2}3^0) = \\
&= 4 \cdot (3^{n-1} \cdot (\frac{0- 2}{2}) + \dots + 3^0 \cdot \frac{(n-1)-1}{2}) = \\
&= 4 \cdot (-\frac{2}{2}3^{n-1} + \dots + \frac{n-2}{2}) 
\end{align}
And I made sum function out of it:
$\sum^{n-1}_{i=0}{\frac{i - 2}{2}\cdot 3^{n-1-i}}$
What to do next? Did I go the wrong direction anywhere?
Thank you for your fast responses.
 A: I think you can just use an induction proof, since you already have an intuition of the result, it is much easier to check :
$$\text{Let : } H_n :"w_n=f(n)-g(n)=4-4n" $$
First, for $n=0$ :
$$w_0=4=4-4\times 0 $$
Hence, $H_0$ is true.
Let $n\in\mathbb{N} $, such that $H_n$ is true, let us show $H_{n+1}$
$$w_{n+1}=3w_n+8n-12=3(4-4n)+8n-12\\
= 12-12n+8n-12=-4n=4-4(n+1) $$
Hence, $H_{n+1} $ is true, so we can conclude that :
$$\forall n \in \mathbb{N}, f(n)-g(n)=4-4n $$
A: $$d(n+1)=3d(n)+8n-12,\\d(0)=4.$$
The homogeneous solution is
$$d_h(n)=3^nd_h(0).$$
Plugging the initial condition,
$$3^0d_h(0)=3\cdot4+8\cdot0-12=0.$$
Then with the ansatz $d_a(n)=an+b,$
$$an+a+b=3an+3b+8n-12$$ or by identification,$$d_a(n)=4-4n=d(n).$$
A: There is no need for induction, use a straight proof.
The equation is
$$f(n+1)-g(n+1)=3(f(n)-g(n))+8n-12$$ with $$f(0)-g(0)=4$$ and it does verify the solution
$$f(n)-g(n)=4-4n$$ as is shown by substitution,
$$4-4(n+1)=3(4-4n)+8n-12,$$ equivalent to $$-4n=-4n.$$
Furthermore, $$4=4-4\cdot 0.$$
A: So, denoting $w_n = f_n -g _n$, you can write down the equation
\begin{align}
w_0 = f_0-g_0 = 4, \qquad &w_{n+1} = f_{n+1}-g_{n+1} = 3(f_n-g_n)+8n -12, \quad\text{i.e.}\\
w_0 = 4, \qquad &w_{n+1} = 3 w_n +8n -12.
\end{align}
This a liner difference equation for which you can have an explicit solution, in the same way that you could have computed explicitly $f_n$ and $g_n$ right from the beginning.
The general solution of the homogeneous equation $w_{n+1} = 3 w_n$ is $w_n^h = c 3^n$, and if you search for a particular solution of the form $w_n^*  =  a n + b$, you'll get $w_n^* = 4 - 4n$. So the general solution is
$$
w_n = c 3^n +4 -4n.
$$
Finally, using the initial condition $w_0=4$, we get $c=0$ and the solution is $w_n = 4 - 4n$.
A: This is an elegant problem. You can use induction on the difference and skip the brute force computation.
Proof by induction:
Let S(n) be the claim that $f(n)-g(n)=4-4n$.
Base case: trivial.
Inductive case: Suppose S(n-1) is true. That is, suppose $f(n-1)-g(n-1)=4-4(n-1)$. Then $f(n)-g(n)=[3f(n-1)+8(n-1)]-[3g(n-1)+12]=3[f(n-1)-g(n-1)]+8n-20.  
$
By induction, that equals:$3[4-4(n-1)]+8n-20=12-12(n-1)+8n-20=12-12n+12+8n-20=24-4n-20=4-4n$
and you're done.
