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
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.
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.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With