Finding Formula for recursive definitions

[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 can't seem to figure a formula for this. Any help, much appreciated!

 

[Mark44]

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.

 

[caseyd1981]

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

 

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

 

[Mark44]

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

 

[caseyd1981]

That is it! Thank you all very much.

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

 

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