# Recursive formulae

1. Mar 6, 2008

### Goldenwind

[SOLVED] Recursive formulae

1. The problem statement, all variables and given/known data
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

3. 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?

2. Mar 6, 2008

Yes. It is.

3. Mar 6, 2008

### Goldenwind

How would I "prove" these to be equivalent?

4. Mar 6, 2008

### e(ho0n3

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

5. Mar 7, 2008

### Goldenwind

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?

6. Mar 7, 2008

### e(ho0n3

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?

7. Mar 7, 2008

### Goldenwind

My book says,
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.

8. Mar 7, 2008

### Goldenwind

It actually goes:
Code (Text):
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.

9. Mar 7, 2008

### Ben Niehoff

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.

10. Mar 7, 2008

### Ben Niehoff

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]$$

11. Mar 8, 2008

### HallsofIvy

Staff Emeritus
Divide it into three cases: n= 3k, n= 3k+1, n= 3k+ 2.

12. Mar 8, 2008

### Goldenwind

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?

13. Mar 8, 2008

### HallsofIvy

Staff Emeritus
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: Mar 8, 2008
14. Mar 8, 2008

### Goldenwind

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: Mar 8, 2008
15. Mar 8, 2008

### HallsofIvy

Staff Emeritus
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.