How to calculate the explicit form of a recursive function?

Question

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

Solution 1

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

Solution 2

Ok, I know you didn't want generating functions (GF from now on) and all the complicated stuff, but my problem turned out to be nonlinear and simple linear methods didn't seem to work. So after a full day of searching, I found the answer and hopefully these findings will be of help to others.

My problem: a[n+1]= a[n]/(1+a[n]) (i.e. not linear (nor polynomial), but also not completely nonlinear - it is a rational difference equation)

1. if your recurrence is linear (or polynomial), wikihow has step-by-step instructions (with and without GF)
2. if you want to read something about GF, go to this wiki, but I didn't get it till I started doing examples (see next)
3. GF usage example on Fibonacci
4. if the previous example didn't make sense, download GF book and read the simplest GF example (section 1.1, ie a[n+1]= 2 a[n]+1, then 1.2, a[n+1]= 2 a[n]+1, then 1.3 - Fibonacci)
5. (while I'm on the book topic) templatetypedef mentioned Concrete Mathematics, download here, but I don't know much about it except it has a recurrence, sums, and GF chapter (among others) and a table of simple GFs on page 335
6. as I dove deeper for nonlinear stuff, I saw this page, using which I failed at z-transforms approach and didn't try linear algebra, but the link to rational difference eqn was the best (see next step)
7. so as per this page, rational functions are nice because you can transform them into polynomials and use linear methods of step 1. 3. and 4. above, which I wrote out by hand and probably made some mistake, because (see 8)
8. Mathematica (or even the free WolframAlpha) has a recurrence solver, which with RSolve[{a[n + 1] == a[n]/(1 + a[n]), a[1] == A}, a[n], n] got me a simple {{a[n] -> A/(1 - A + A n)}}. So I guess I'll go back and look for mistake in hand-calculations (they are good for understanding how the whole conversion process works).

Anyways, hope this helps.

Solution 3

In general, there is no algorithm for converting a recursive form into an iterative one. This problem is undecidable. As an example, consider this recursive function definition, which defines the Collatz sequence:

f(1) = 0
f(2n) = 1 + f(n)
f(2n + 1) = 1 + f(6n + 4)

It's not known whether or not this is even a well-defined function or not. Were an algorithm to exist that could convert this into a closed-form, we could decide whether or not it was well-defined.

However, for many common cases, it is possible to convert a recursive definition into an iterative one. The excellent textbook Concrete Mathematics spends much of its pages showing how to do this. One common technique that works quite well when you have a guess of what the answer is is to use induction. As an example for your case, suppose that you believe that your recursive definition does indeed give 3^n - 1. To prove this, try proving that it holds true for the base cases, then show that this knowledge lets you generalize the solution upward. You didn't put a base case in your post, but I'm assuming that

f(0) = 0
f(1) = 2

Given this, let's see whether your hunch is correct. For the specific inputs of 0 and 1, you can verify by inspection that the function does compute 3^n - 1. For the inductive step, let's assume that for all n' < n that f(n) = 3^n - 1. Then we have that

f(n) = 2f(n - 1) + 3f(n - 2) + 4
     = 2 * (3^{n-1} - 1) + 3 * (3^{n-2} - 1) + 4
     = 2 * 3^{n-1} - 2 + 3^{n-1} - 3 + 4
     = 3 * 3^{n-1} - 5 + 4
     = 3^n - 1

So we have just proven that this recursive function does indeed produce 3^n - 1.

Comments

[atoMerz]

Thank you templatetypedef, but induction and proving my guess isn't what I'm looking for. In this special case I guessed the answer, but I'm looking for a way to find it mathematically. However, I want it to be as simple as possible(?).

[atoMerz]

Thanks for sharing, useful links.