# Solve Recursive Formulae: (-1)^n

• Goldenwind
In summary, the author provides four recursive definitions of a function from the set of nonnegative integers to the set of integers. The first definition is a well defined recursive definition, while the other three definitions are not well defined. Each recursive definition can be solved using a standard method of solving recurrence relations.
Goldenwind
[SOLVED] Recursive formulae

## Homework Statement

Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid.

a) f(0) = 1, f(n) = -f(n – 1) for n >= 1

## The Attempt at a Solution

f(1) = -f(1 – 1) = -f(0) = -1
f(2) = -f(2 – 1) = -f(1) = 1
f(3) = -f(3 – 1) = -f(2) = -1

I can see that it is a valid recursive definition.
Why is it asking me to find a formula for f(n), when we were given it (= -f(n-1))?
Are they asking for a nonrecursive formula that also applies?

In this case, it would be f(n) = (-1)^n.
Is this what they want?

Yes. It is.

How would I "prove" these to be equivalent?

You mean prove that f(n) = (-1)^n? Use induction.

One of the questions I'm now facing, I can't answer with one formulae. f(2k) = 0, regardless of k, and f(2k+1) keeps doubling. I could possibly use two formulae, one for even, one for odd, but is this what I am to do, or is this considered a "not well defined" function?

Consider both even and odd cases as you have already pointed out. Ask yourself this: If it isn't well defined, for what values of the argument is it not well defined?

My book says,
Recursively defined functions are well defined. That is, for every positive integer, the value of the function at this integer is determined in an umambiguous way. This means that given any positive integer, we can use the two parts of thye definition to find the value of the function at that integer, and that we obtain the same value no matter how we apply the two parts of the definition. This is a consequence of the principle of mathematical induction.

Unsure about "well" defined, but the formula is "defined" for all positive integers.
For reference, it's:
f(0) = 1, f(1) = 0, f(2) = 2, f(n) = 2f(n – 3) for n >= 3

From which, you see at pattern of:
1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, etc.

It actually goes:
Code:
   n = 0, 1, 2, 3, 4, 5, 6
f(n) = 1, 0, 2, 2, 0, 4, 8

This makes it even harder to make a formula for.

There is a standard method of solving recurrence relations. Is your course not teaching it? It works like this:

Try a solution of the form

$$F(n) = r^n$$

where r is some number yet to be determined. Now, plug this into your recurrence relation, and you will get an algebraic equation for r. For example, suppose you have the Fibonacci sequence:

$$F(n) = F(n-1) + F(n-2)$$

Plugging in $F(n) = r^n$, we get

$$r^n = r^{n-1} + r^{n-2}[/itex] Now, simply divide both sides by $r^{n-2}$ and move everything to the left side to get a quadratic equation in r: [tex]r^2 - r - 1 = 0$$

Solving this for r, you obtain

$$r = \frac{1\pm\sqrt5}2$$

(note: if you take the plus sign, you get the Golden Ratio!). Now, since you have two different solutions, you can try a linear combination of them:

$$F(n) = Ar_1^n + Br_2^n$$

In order to find A and B, you use your initial values:

$$F(0) = 1$$
$$F(1) = 1$$

which will lead to a system of two linear equations to solve for A and B.

Note that if you DID have a sequence like

$$1, 0, 2, 0, 4, 0, 8, ...$$

then you can proceed by noting that this is a sum of two sequences:

$$\frac12, \frac{\sqrt2}2, 1, \frac{\sqrt8}2, 2, \frac{\sqrt{32}}2, 4, ...$$
$$\frac12, -\frac{\sqrt2}2, 1, -\frac{\sqrt8}2, 2, -\frac{\sqrt{32}}2, 4, ...$$

and then you can write down the answer as

$$\frac12\left[(\sqrt2)^n + (-\sqrt2)^n\right]$$

Goldenwind said:
It actually goes:
Code:
   n = 0, 1, 2, 3, 4, 5, 6
f(n) = 1, 0, 2, 2, 0, 4, 8

This makes it even harder to make a formula for.
Divide it into three cases: n= 3k, n= 3k+1, n= 3k+ 2.

But the thing is, I only need to do this work if it is "well defined". But, all of the questions seem "well defined", which throws me off =/

a) f(0) = 1, f(n) = -f(n – 1) for n >= 1
b) f(0) = 1, f(1) = 0, f(2) = 2, f(n) = 2f(n – 3) for n >= 3
c) f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n >= 2
d) f(0) = 0, f(1) = 1, f(n) = 2f(n – 1) for n >= 1
e) f(0) = 2, f(n) = f(n – 1) if n is odd and n >= 1 and f(n) = 2f(n – 2) if n >= 2

They all seem to be valid to me...
Should I just ignore the "well defined" part and do it anyway?

Well, you could go ahead and try to find a "closed form" formula for f(n). If you can then the recursive formula must be "well defined"!

In (c), you have "f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n >= 2". What is f(2)? How would you find f(3)?

Last edited by a moderator:
f(2) = 2f(3), but we don't have f(3), so we switch things a bit.
f(n) = 2f(n+1)
f(n)/2 = f(n+1)
Which I believe would be the same as f(n-1)/2 = f(n)

Plug in 2 for n, and you get...
f(2) = f(1)/2 = 1/2
For n=3, f(3) = f(2)/2 = 1/4

So a formula for this could be something similar to $$f(0) = 0, f(n) = \frac{1}{2^{n-1}}$$ for n $\geq 1.$.

Last edited:
HallsofIvy said:
Well, you could go ahead and try to find a "closed form" formula for f(n). If you can then the recursive formula must be "well defined"!

In (c), you have "f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n >= 2". What is f(2)? How would you find f(3)?

Goldenwind said:
f(2) = 2f(3), but we don't have f(3), so we switch things a bit.
f(n) = 2f(n+1)
f(n)/2 = f(n+1)
Which I believe would be the same as f(n-1)/2 = f(n)

Plug in 2 for n, and you get...
f(2) = f(1)/2 = 1/2
For n=3, f(3) = f(2)/2 = 1/4

So a formula for this could be something similar to $$f(0) = 0, f(n) = \frac{1}{2^{n-1}}$$ for n $\geq 1.$.
Very nice. But f(n)= 2f(n+1) is only defined for n>= 2 so that f(n-1)= 2f(n) and then f(n)= (1/2)f(n-1) is only defined for n-1>= 2 or n>= 3.

## 1. What is a recursive formula?

A recursive formula is a mathematical formula that defines a sequence or function based on previous terms or values. It refers to the process of repeating a procedure or calculation using the result of the previous iteration.

## 2. How do you solve a recursive formula?

To solve a recursive formula, you can either use a general formula or a recursive algorithm. A general formula involves finding a pattern and writing an equation to represent it, while a recursive algorithm involves breaking down the problem into smaller, simpler steps and using the previous result to find the next one.

## 3. What does (-1)^n mean in a recursive formula?

In a recursive formula, (-1)^n represents the alternating sign of each term in the sequence. It means that the terms will alternate between positive and negative values as n (the index or position of the term) increases.

## 4. Can you give an example of solving a recursive formula (-1)^n?

Sure, for example, if we have the recursive formula a[n] = a[n-1] * (-1)^n with a[0] = 2, we can solve it by plugging in the values of n starting from 1. So, a[1] = a[0] * (-1)^1 = 2 * (-1) = -2, a[2] = a[1] * (-1)^2 = -2 * (1) = 2, and so on.

## 5. What are some real-life applications of recursive formulae?

Recursive formulae are commonly used in computer programming, such as in algorithms for sorting and searching data. They are also used in finance and economics to model compound interest and population growth. Additionally, they can be used in physics to describe natural phenomena, such as the Mandelbrot set in chaos theory.

• Calculus and Beyond Homework Help
Replies
11
Views
561
• Calculus and Beyond Homework Help
Replies
17
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
749
• Calculus and Beyond Homework Help
Replies
5
Views
865
• Calculus and Beyond Homework Help
Replies
20
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
759
• Calculus and Beyond Homework Help
Replies
3
Views
768
• Calculus and Beyond Homework Help
Replies
6
Views
486
• Calculus and Beyond Homework Help
Replies
8
Views
440
• Calculus and Beyond Homework Help
Replies
6
Views
619