Solve Recursion Equation: f(x)=-f(x-1)+g(x)

[Marth361]

Hi I'm doing a project in math and seem to be stuck on one part.

I come to trying to solve this recursion equation given by...

f(x) = -f(x-1) + g(x) where g(x) is known.

Would anyone mind showing me how to go around solving for f(x)?
In this case i have g(x)=x$$^{2}$$ and f(0)=0 and f(1)=1
but will need to solve for any g(x) later on.

Thank You!

 

[Bill Simpson]

In the textbook "Discrete Mathematics with Proof" by Eric Gossett he describes a fairly simple manual process that can be used to solve some problems like this.

You begin by writing down your expression for f(n)
f(n) = -f(n - 1) + n^2
Then you expand the f(n-1) term using your definition
f(n) = -(-f(n - 2) + (n - 1)^2) + n^2
Then you "gently" simplify this, roughly only trying to isolate the f(n-2) and no more
f(n) = f(n - 2) - (n - 1)^2 + n^2
Now you repeat this pair of steps again, carefully.
f(n) = -(f(n - 3) + (n - 2)^2) - (n - 1)^2 + n^2
f(n) = -f(n - 3) - (n - 2)^2 - (n - 1)^2 + n^2
You repeat this enough times until you see the patterns developing in the result.
With that you make a leap letting you write the pattern reduced all the way to f(1) or f(0).
And finally you look at the pattern and try to see a simpler closed form expression.

So try to apply this description on your problem and see how much progress you can make. There are other, sometimes more powerful, methods of solving these, but this method may make some sense to you and can be used to solve some problems like yours. Be very careful to not make mistakes with subscripts and signs when you are doing this.

 

[Marth361]

I can see where you are going with this but wouldn't I arrive at f(n) being equal to some sum.
I believe it would come out to be...

f(n)=n$$^{2}$$-$$\sum$$i$$^{2}$$ from i=1 to i=n-1

If this is the case than any g(x) will involve me finding the partial sum of some series. Which is easy in this case but id rather avoid that situation for further instances of g(x)

 

[Bill Simpson]

I think it is good that you were able to see where to go from the hint that I provided.
The form of the result will obviously depend heavily on what g(x) is. Like integrals and differential equations, there are recurrence relations that do not have simple closed form solutions, but for many simple problems we find there is a compact solution. If you want to learn more about this then "Concrete Mathematics" by Graham and Knuth is one introduction. The author of "Generatingfunctionology" kindly put a pdf copy of his latest edition on the web. That would take more work to master, but is not beyond reach of the dedicated.