Question

Find u(n):
u(0)=1, u(1)=16, u(n+2)=8*u(n+1)-16u(n)

Answer 1

I don't know what methods are available to you, so I'll just use one that I'm comfortable with: generating functions. It's a bit tedious, but it works! If you don't know it, there's no harm in learning about it.

Let U(x) be the generating function for the sequence u(n), i.e.

`\displaystyle U(x) = \sum_(n=0)^\infty u(n)x^n`

In the recurrence equation, we multiply both sides by xⁿ (where |x| < 1, which will come into play later), then take the sums on both sides from n = 0 to ∞, thus recasting the equation as

`\displaystyle \sum_(n=0)^\infty u(n+2) x^n = 8 \sum_(n=0)^\infty u(n+1) x^n - 16 \sum_(n=0)^\infty u(n) x^n`

Next, we rewrite each sum in terms of U(x). For instance,

`\displaystyle \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2} \sum_(n=0)^\infty u(n+2) x^(n+2) \\\\ \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2} \bigg(u(2)x^2 + u(3)x^3 + u(4)x^4 + \cdots \bigg) \\\\ \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2} \sum_(n=2)^\infty u(n) x^n \\\\ \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2} \left(\sum_(n=0)^\infty u(n) x^n - u(1)x - u(0)\right) \\\\ \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2}(U(x) - 16x - 1) \\\\ \sum_(n=0)^\infty u(n+2) x^n = \frac1{x^2}U(x) - \frac{16}x - \frac1{x^2}`

After rewriting each sum in a similar way, we end up with a linear equation in U(x),

`\displaystyle \frac1{x^2}U(x) - \frac{16}x - \frac1{x^2} = \frac8x U(x) - \frac8x - 16 U(x)`

Solve for U(x) :

`\displaystyle \left(\frac1{x^2}-\frac8x+16\right) U(x) = \frac1{x^2} + \frac8x \\\\ \left(1-8x+16x^2\right) U(x) = 1 + 8x \\\\ (1-4x)^2 U(x) = 1 + 8x \\\\ U(x) = (1+8x)/((1-4x)^2)`

The next step is to get the power series expansion of U(x) so that we can easily identity u(n) as the coefficient of the n-th term in the expansion.

Recall that for |x| < 1, we have

`\displaystyle \frac1{1-x} = \sum_(n=0)^\infty x^n`

By differentiating both sides, we get

`\displaystyle \frac1{(1-x)^2} = \sum_(n=0)^\infty nx^(n-1) = \sum_(n=1)^\infty nx^(n-1) = \sum_(n=0)^\infty (n+1)x^n`

It follows that

`\displaystyle \frac1{(1-4x)^2} = \sum_(n=0)^\infty (n+1)(4x)^n`

and so

`\displaystyle (1+8x)/((1-4x)^2) = \sum_(n=0)^\infty (n+1)(4x)^n + 8x\sum_(n=0)^\infty (n+1)(4x)^n \\\\ (1+8x)/((1-4x)^2) = \sum_(n=0)^\infty 4^n(n+1)x^n + 2\sum_(n=0)^\infty 4^(n+1)(n+1)x^(n+1) \\\\ (1+8x)/((1-4x)^2) = \sum_(n=0)^\infty 4^n(n+1)x^n + 2\sum_(n=1)^\infty 4^nnx^n \\\\ (1+8x)/((1-4x)^2) = \sum_(n=0)^\infty 4^n(n+1)x^n + 2\sum_(n=0)^\infty 4^nnx^n \\\\ (1+8x)/((1-4x)^2) = \sum_(n=0)^\infty 4^n(3n+1)x^n`

which means

`u(n) = \boxed{4^n(3n+1)}`