Solve Recursive Formulae: (-1)^n

[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?

 

[e(ho0n3]

Yes. It is.

 

[Goldenwind]

How would I "prove" these to be equivalent?

 

[e(ho0n3]

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

 

[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?

 

[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?

 

[Goldenwind]

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.

 

[Goldenwind]

Made a mistake.
It actually goes:

   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.

 

[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

[tex]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:

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

 

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

 

[HallsofIvy]

Made a mistake.
It actually goes:

   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.

 

[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?

 

[HallsofIvy]

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]

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

 

[HallsofIvy]

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)?

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.