Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to calculate the explicit form of a recursive function?

I have this recursive function:

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
f(1) = 2
f(2) = 8

I know from experience that explicit form of it would be:

f(n) = 3 ^ n - 1  // pow(3, n) - 1

I wanna know if there's any way to prove that. I googled a bit, yet didn't find anything simple to understand. I already know that generation functions probably solve it, they're too complex, I'd rather not get into them. I'm looking for a simpler way.

P.S. If it helps I remember something like this solved it:

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
// consider f(n) = x ^ n
x ^ n = 2 * x ^ (n-1) + 3 * x ^ (n-2) + 4

And then you somehow computed x that lead to explicit form of the recursive formula, yet I can't quite remember

like image 787
atoMerz Avatar asked Apr 23 '11 18:04

atoMerz


People also ask

What is the formula for explicit formula?

The explicit formula for an arithmetic sequence is an = a + (n - 1)d, and any term of the sequence can be computed, without knowing the other terms of the sequence. In general, the explicit formula is the nth term of arithmetic, geometric, or harmonic sequence.

What is the formula for recursive form?

A recursive formula is a formula that defines any term of a sequence in terms of its preceding term(s). For example: The recursive formula of an arithmetic sequence is, an = an-1 + d. The recursive formula of a geometric sequence is, an = an-1r.


1 Answers

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4
f(n+1) = 2 * f(n) + 3 * f(n-1) + 4

f(n+1)-f(n) = 2 * f(n) - 2 * f(n-1) + 3 * f(n-1) - 3 * f(n-2)
f(n+1) = 3 * f(n) + f(n-1) - 3 * f(n-2)

Now the 4 is gone. As you said the next step is letting f(n) = x ^ n

x^(n+1) = 3 * x^n + x^(n-1) - 3 * x^(n-2)

divide by x^(n-2)

x^3 = 3 * x^2 + x - 3
x^3 - 3 * x^2 - x + 3 = 0

factorise to find x

(x-3)(x-1)(x+1) = 0
x = -1 or 1 or 3

f(n) = A * (-1)^n + B * 1^n + C * 3^n
f(n) = A * (-1)^n + B + C * 3^n

Now find A,B and C using the values you have

f(1) = 2; f(2) = 8; f(3) = 26

f(1) = 2 = -A + B + 3C
f(2) = 8 = A + B + 9C
f(3) = 26 = -A + B + 27C

solving for A,B and C:

f(3)-f(1) = 24 = 24C      => C = 1
f(2)-f(1) = 6 = 2A + 6    => A = 0
2 = B + 3                 => B = -1

Finally

f(n) = 3^n - 1
like image 193
Alex Avatar answered Oct 20 '22 12:10

Alex