3

Given the recursion

$f(n) = 6f(n-1) - 12f(n-2) + 8f(n-3)$ for $n \ge 3, f(0) = 1, f(1) = 0, f(2) = 1$,

find an explicit form for $f(n)$.

I already solved this excercise in the past, but the solutions I received didn't involve fractions (as they do now), so I believe that I make a mistake at some point.

The equation above is equivalent to

$$f(n+3) - 6f(n+2) + 12f(n+1) - 8f(n) = 0 \ for \ n \ge 0.$$

We identify the polynomial

$$q(z) = z^3 - 6z^2 + 12z - 8 = (z-2)^3.$$

We see that $z = 2$ is the only root with an algebraic multiplicity of $3$, hence, we receive

$$f(n) = (a + bn + cn^2)2^n.$$

Plugging the values in gives us

$$f(0) = a = 1,$$

$$f(1) = (1 + b + c)2 = 0 \equiv 1 + b + c = 0 \equiv c = -1 - b,$$

$$f(2) = (1 + 2b + 4c)4 = 1 \equiv (1 + 2b + 4(-1-b))4 = 1 \equiv -8b = 13 \ \equiv b = - 13/8,$$

which makes $c$ a fraction too. Any ideas were I am wrong here? As I said, I didn't receive any fractions the last time I solved it (but maybe I was actually wrong there, who knows).

Community
  • 1
Julian
  • 1,401

1 Answers1

3

the solution is given by $$a_n=2^{n-3} \left(5 n^2-13 n+8\right)$$ can you get it from here?

Dr. Sonnhard Graubner
  • 95,283
  • Well, this is exactly the solution I receive when I write $f(n)$ explicitly with the values from above. If this is indeed the correct solution here, I guess I actually made a mistake the last time when I received values without a fraction. Thanks! – Julian Sep 16 '17 at 10:52
  • ok the main Thing is you have got your solution – Dr. Sonnhard Graubner Sep 16 '17 at 10:52