Finding Formula for recursive definitions

1. Mar 8, 2009

caseyd1981

This is the last part of the problem and I just can not figure out a formula for it. Here is what the question asks:

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.

I'm stuck on part 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

I've worked through f(0) - f(9) and I get 2, 2, 4, 4, 8, 8, 16, 16, 32, 32. I just cant seem to figure a formula for this. Any help, much appreciated!

2. Mar 8, 2009

Staff: Mentor

Are you sure that you have written the definition of the function correctly?
In particular, it seems that the second part should say that f(n) = 2f(n - 2) if n is even and n >= 2.

3. Mar 8, 2009

caseyd1981

Yes, that is correct. I noticed that too but I typed it exactly the way my book did.

4. Mar 8, 2009

Dick

Have you defined a floor function? Something like [x]=greatest integer less than or equal to x? That would help you to write it concisely. [n/2] has something in common with your function.

5. Mar 8, 2009

Staff: Mentor

It looks to me like this might work as a non-recursive definition for your function:
f(x) = 2^$\left\lfloor(x + 2)/2 \rfloor\right$

The L-shaped brackets indicate the greatest integer function, which is the greatest integer that is less than or equal to what's inside the brackets.

If the expression in the exponent is an integer, the greatest integer function evaluates to that integer. If the exponent is a non-integer, the greatest integer function essentially chops off the fractional part. For example, the greatest integer in 1 is 1. The greatest integer in 1.5 is 1.

Using the formula above as a check, f(0) = 2^$\left\lfloor(0 + 2)/2 \rfloor\right$
= 2^1 = 2
f(1) = 2^$\left\lfloor(1 + 2)/2 \rfloor\right$
= 2^$\left\lfloor(3)/2 \rfloor\right$ = 2^1 = 2

f(2) = 2^$\left\lfloor(2 + 2)/2 \rfloor\right$ = 2^2 = 4
f(3) = 2^$\left\lfloor(3 + 2)/2 \rfloor\right$ = 2^$\left\lfloor 5/2 \rfloor\right$ = 2^2 = 4

6. Mar 8, 2009

caseyd1981

That is it! Thank you all very much.

Ok, now I need to prove the formula using induction. Kind of stuck there too....?

7. Mar 30, 2009

papatrpt89

Hello,

I'm in a class that uses the same textbook as caseyd1981. I'm working on this exact same problem. Through looking at relationships between powers of 2 and values of n, I've come up with an explicit formula:
f(n) = $\left\lceil(n + 1)/2 \rceil\right$

Now, I need to prove it using induction (I'm not sure whether it needs to be mathematical induction or strong induction).

So far, I have this:
Basis case:
f(1) = 2^$\left\lceil(1 + 1)/2 \rceil\right$ = 2^$\left\lceil(2)/2 \rceil\right$ = 2^1 = 2.
Inductive hypothesis:
if f(n) = 2^$\left\lceil(n + 1)/2 \rceil\right$, then f(n+1) = 2^$\left\lceil((n + 1) + 1) / 2\rceil\right$.

However, I'm stuck here, as I don't know how to incorporate the inductive hypothesis f(n) = $\left\lceil(n + 1)/2 \rceil\right$ into f(n+1) = 2^$\left\lceil((n + 1) + 1) / 2\rceil\right$.

Anyone have any suggestions? Thanks for your time!

Last edited: Mar 30, 2009