# Simplifying a recursive function

1. Apr 10, 2007

### randommacuser

I am trying to find a formula for f(x) = a*f(x-1) + b*f(x-2) for x≥1, assuming f(-1) and f(0) are known. In other words, I need some expression for f(x) just in terms of a, b, f(-1), and f(0).

I tried plugging in stuff and factoring on paper for the first few iterations, but it quickly got out of control. Then I let Mathematica do the grunt work and tried to see some patterns as x increases. But so far I am only seeing the obvious first couple of terms: a^x * f(0) - (x-1) * a^(x-1) * b * f(0)

Any clues? Should I even be doing the problem this way, or is there some simpler method?

Last edited: Apr 10, 2007
2. Apr 10, 2007

### moe_3_moe

just a question...the function is x and the variable is n?

3. Apr 10, 2007

### randommacuser

Well, that was the way the problem was stated. I've edited the OP to make it more standard. Now f is a function of the variable x, as usual.

4. Apr 10, 2007

### moe_3_moe

hey man did u try to get f(1) and then replace it in f(2) and so on u will find a relation between f(2) with just f(0) and f(-1) in it with some factorize and like that ... try it

5. Apr 10, 2007

### Data

Try substituting $f(x) = m^x$ for some m, and see where that gets you (this is a standard method for solving homogeneous constant coefficient linear recurrences. It's analogous to solving homogeneous constant coefficient linear ODEs using an exponential substitution).

Last edited: Apr 10, 2007
6. Apr 10, 2007

### randommacuser

moe_3_moe: Yes, I did this by hand to about f(5) and on Mathematica to f(10). But the goal is one expression of f(x), for all x, in terms of the four given parameters.

7. Apr 10, 2007

### moe_3_moe

ok get it ... let's see what we can do ... at least now we know how mathematica works hard lol ...

8. Apr 10, 2007

### moe_3_moe

data...can we have more details about ur suggestion

9. Apr 10, 2007

### Data

Using that substitution you can find the values for m that give you solutions. There will be two of them. The general solution is a linear combination of the two; use the given values for f(0) and f(-1) to find the particular solution.

10. Apr 10, 2007

### moe_3_moe

right thanks ..it did work ...

11. Apr 10, 2007

### randommacuser

Perfect. Thanks for your help, Data.