How To Solve $f(n)=6f(n-1)-8f(n-2)+7*2^{4n-8}-3*2^{3n-5}$

Question

The initial values are $f(0)=f(1)=0$. Are there any relatively simple ways to solve the problem? I am almost certain that the solution is, $\frac {2^n(2^n - 1)(2^n - 2)(2^n - 3)}{24}$, but I don't know how to solve it since I couldn't think of any ways to turn it into a diagonalizable matrix. If this requires anything beyond simple linear algebra to solve, it would be nice if you could give an overview of the method or a link to an explanation since I am stuck on this problem.

Answer 1

The given recurrence is a linear recurrence of level / order two for the sequence $$(\ f(n)\ )_{n\ge 0}\ , $$ with constant coefficients but containing also some "distortion" terms. It is important in the sequel that these terms that break the linearity are a linear combination of functions of the form $P(n)a^n$, where $P$ is a polynomial, $a$ a constant. (There may occur different polynomials $P_1,P_2,\dots$, and different constants $a_1,a_2,\dots$) Then the given sequence satisfies a linear recurrence relation of higher degree.

See also Recurrence relation.

In our case, the L.H.S. in $$f(n)-6f(n-1)+8f(n-2)=g(n)$$ "admits a characteristic polynomial" $X^2-6X+8$ with the roots $2,4$. This is not OK, of course, but imagine we solve first the homogenous problem, as we often do with linear systems and differential equations.

The R.H.S. has the form $g(n)=C\cdot 16^n+D\cdot 8^n$ with suitable constants $C,D$. So it satisfies a linear recursion with characteristic polynomial $(X-16)(X-8)$.

We expect then that $f$ satisfies a linear recursion with characteristic polynomial $$ (X-2)(X-4)(X-8)(X-16)\ , $$ after collecting all involved roots.

---

At this point we may also capture the idea in a simple way. We forget all the above, and start again from zero. Because $(X-8)(X-16)=X^2-24X+128$, we know or show that $g$ satisfies $$ g(n)-24g(n-1)+128g(n-2)=0\ . $$ Consider then $$ F(n) = f(n)-24f(n-1)+128f(n-2)=0\ . $$ Then $F$ satisfies a clean linear recursion, $$ F(n)-6F(n-1)+8F(n-2)\ . $$ We plug in the definition of $F$ via $f$ in the relation above, get a "clean" linear recursion of order four for $f$. It turns out that its coefficients are the ones of the polynomial $(X-2)(X-4)\cdot (X-8)(X-16)$. (Digression: This is explicitly $X^4 - 30X^3 + 280X^2 - 960X + 1024$, but we do not need this, except we really want to check this relation using a computer. This is often done in informatics courses, since one cannot trust mathematics. But (only) after we can implement, and see it works in ten special cases we can trust the scheme suggested in math books.)

From here, $f$ satisfies a formula of the shape $$ f(n)=a2^n+b4^n+c8^n+d16^n\ , $$ and the constants $a,b,c,d$ have to be determined from the "first four conditions". (So we have to compute also $f(2)$, $f(3)$ from the given recursion.) In our case we have the coefficients $a,b,c,d$, (assamblated and in a factorized expression, that we do not need to expand, since) we need to verify the formula only for $f(0)$, $f(1)$, $f(2)$, $f(3)$.

---

Later EDIT: Let us find the constants $a,b,c,d$ explicitly. To simplify typing and computing, i will use a computer algebra system, here sage.

Let us define $f$ recursively and compute its first values in sage.

sage: def f(n): 
....:     if n == 0:    return 0 
....:     if n == 1:    return 0 
....:     return 6*f(n-1) - 8*f(n-2) + 7*2^(4*n-8) - 3*2^(3*n-5) 
....:
sage: for n in [0..20]:
....:     print("f(%2s) = %s" % (n, f(n)))
f( 0) = 0
f( 1) = 0
f( 2) = 1
f( 3) = 70
f( 4) = 1820
f( 5) = 35960
f( 6) = 635376
f( 7) = 10668000
f( 8) = 174792640
f( 9) = 2829877120
f(10) = 45545029376
f(11) = 730862190080
f(12) = 11710951848960
f(13) = 187512576276480
f(14) = 3001300362981376
f(15) = 48029600424386560
f(16) = 768543969628897280
f(17) = 12297266440393687040
f(18) = 196760766551437541376
f(19) = 3148208293242063421440
f(20) = 50371620920737339801600

We need only the first values to build a linear system in the unknowns $a,b,c,d$, and then having them to insert them as "constants" $a,b,c,d$ in the formula for $f(n)$ for a general $n$. The equations are...

sage: var('a,b,c,d');
sage: eqs = [ a*2^n + b*4^n + c*8^n + d*16^n == f(n) for n in [0,1,2,3] ]
sage: for eq in eqs: 
....:     print(eq) 
....:
a + b + c + d == 0
2*a + 4*b + 8*c + 16*d == 0
4*a + 16*b + 64*c + 256*d == 1
8*a + 64*b + 512*c + 4096*d == 70
sage: solve(eqs, [a,b,c,d])
[[a == (-1/4), b == (11/24), c == (-1/4), d == (1/24)]]

Now we can associate the formula for $f(n)$ and test it, i.e. $$ f(n) = -\frac 14\cdot 2^n +\frac {11}{24}\cdot 4^n -\frac 14\cdot 8^n +\frac {1}{24}\cdot 16^n $$ for the first values of $n$ numerically, which is always a good check to be done.

sage: formula(n) = -1/4*2^n + 11/24*4^n -1/4*8^n + 1/24*16^n
sage: [ bool(f(n) == formula(n)) for n in [0..20] ]
[True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True,
 True]
sage: 

By chance, we can get a factorized expression of the formula. But this is not the case in a general case.