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

• Marth361
In summary, the conversation discusses how to solve a recursion equation with a given g(x) and specific initial values for f(0) and f(1). The suggested method involves expanding and simplifying the equation until a pattern is identified, and then using that pattern to find a simplified closed form expression for f(n). The conversation also mentions that there are other methods for solving these types of equations and suggests further resources for learning about them.
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!

Last edited:
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.

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)

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.

Last edited:

Hello there,

Step 1: Write out the recursive sequence
The first step is to write out the recursive sequence by substituting the values of x. In this case, we have:

f(0) = -f(-1) + g(0)
f(1) = -f(0) + g(1)
f(2) = -f(1) + g(2)
...
f(x) = -f(x-1) + g(x)

Step 2: Use the initial conditions
Since you have been given the initial conditions f(0) = 0 and f(1) = 1, you can use them to solve for the next term in the sequence. In this case, you can use f(0) = 0 to solve for f(1) and then use f(1) = 1 to solve for f(2), and so on.

Step 3: Substitute the values
Once you have solved for the initial conditions, you can substitute them into the recursive equation to find the next term in the sequence. For example, using f(0) = 0, we can solve for f(1) as follows:

f(1) = -f(0) + g(1)
f(1) = -0 + g(1)
f(1) = g(1)
Therefore, f(1) = g(1).

Step 4: Continue solving
You can continue this process to find the values for f(2), f(3), and so on until you reach the desired value of x.

In this case, since g(x) = x^2, the sequence will look like this:

f(0) = 0
f(1) = g(1) = 1^2 = 1
f(2) = -f(1) + g(2) = -1 + 2^2 = 3
f(3) = -f(2) + g(3) = -3 + 3^2 = 6
f(4) = -f(3) + g(4) = -6 + 4^2 = 10
...

Therefore, the general formula for f(x) in terms of g(x) would be:

f

## 1. What is a recursion equation?

A recursion equation is a mathematical formula that defines a sequence of numbers or values by using one or more previous values in the sequence. It is a way of defining a function in terms of itself.

## 2. What does f(x) = -f(x-1) + g(x) mean in a recursion equation?

This equation means that the value of the function at a certain point (f(x)) is equal to the negative of the value of the function at the previous point (f(x-1)) plus the value of another function (g(x)) at the current point. This is a common form of recursion equation that involves two functions.

## 3. How do you solve a recursion equation?

In order to solve a recursion equation, you need to find a pattern in the values of the function and use that pattern to generate a formula or algorithm. This can often be done by examining the first few values of the function and looking for a relationship between them. Once a formula is found, it can be used to calculate any value of the function.

## 4. What is the purpose of using recursion in equations?

Recursion is often used in equations to define a function in a simpler way. By using recursion, we can break down a complex problem into smaller, more manageable parts. This can make it easier to solve problems that would be difficult or impossible to solve using other methods.

## 5. Can recursion equations be used in real-life applications?

Yes, recursion equations have many real-life applications in fields such as computer science, engineering, and economics. They can be used to model patterns in data, analyze complex systems, and optimize processes. Some common examples of recursion equations in real life include the Fibonacci sequence, fractals, and recursive algorithms in computer programming.

Replies
2
Views
1K
Replies
9
Views
1K
Replies
1
Views
877
Replies
1
Views
851
Replies
19
Views
2K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
6
Views
2K
Replies
3
Views
1K
Replies
2
Views
1K