b = 4^(2k), where k is an integer?

and the >0 thing is referring to b, as in, b must be > 0? Although that goes without saying if it's as I assume...

Edit: maybe the >0 thing is referring to k

makes a lot more sense to me that way actually

This post was edited by Generator on Oct 6 2013 12:53am

yeah I think you have penetrated the fog.

Are you sure it's an even power of 4 and not an even power of 2 (which would be an integer power of 4)? Maybe I'm just an idiot, but it doesn't look like it can be solved in the typical recursive fashion as is. Regardless, please re-post the question verbatim.

This post was edited by Generator on Oct 6 2013 01:47am

Except 4^(2*3) != 4^(2*2) + 4^(1*2) So this is more complicated than it initially sounded. The only reason I could think of that they would give A(1) is if they wanted you to use this:

A(4) = A(2) + A(1)

A(4) = A(2) + 1

So that might be a clue of some sort.

k>=0 because we have A(1).

b = 4^2k

Yes I'm looking for a closed form for the recurrence relation.



Lets suppose b is an even power of 2 if it makes it easier?

This post was edited by MsRailgun on Oct 6 2013 08:29am

A(1) = 1, also prevents you from using a trivial function like:
A(b) = 0

This post was edited by Azrad on Oct 6 2013 11:57am

Let me try to rephrase the problem :

you want to find a function A such that :
A(1) = 1
A(4) = A(2) + A(1)
A(16) = A(8) + A(4)
A(64) = A(32) + A(16)
etc
and with no condition whatsoever on every A(n) with n not of the form 2^k ?

In this case, the function is almost entirely free. Only A(4), A(16), A(64) etc have an expression in terms of previous values.

For example, A(1) = A(4) = A(16) = A(64) = ... = 1, A(n) = 0 for every other n.

I guess there must be some extra constraint.

If you were asked also to have A(4b) = A(2b) + A(b) for every b = 2^k, then the problem would be a little more exciting :

A(1) = 1
A(2) = ?
A(4) = A(2) + A(1) = ? + 1
A(8) = A(4) + A(2) = 2? + 1
A(16) = A(8) + A(4) = 3? + 2
A(32) = A(16) + A(8) = 5? + 3
A(64) = A(32) + A(16) = 8? + 5
etc

A(2^k) = u(k-1) * ? + u(k-2) for every natural k>1, where u is the Fibonacci sequence :
u0 =1, u1=1, u2=2, u3=3, u4=5, u5=8, u6=13,... each term being the sum of the 2 previous terms.

To get an expression of u(n) in terms of n, solve the general recursive relation : u(n+2) = u(n+1) + u(n), using the quadratic : X² = X + 1
Roots are :
Phi = (1+sqrt(5)) / 2
Phi' = (1-sqrt(5)) / 2

Notice that Phi is known as the golden ratio (and Phi' is its conjugate).

Particular solutions to your recursive relation are :
f(n) = Phi ^ n
g(n) = Phi' ^ n

and the general solution is :
h(n) = C. Phi ^ n + D. Phi' ^ n, where C and D are some constants, that you can find by plugging in the initial terms of your sequence.

In this case :
C + D = 1
C.Phi + D.Phi' = 1
so :
C = (5+sqrt(5)) / 10
D = (5-sqrt(5)) / 10

Conclusion :
u(n) = (5+sqrt(5) / 10 * Phi ^ n + (5-sqrt(5)) / 10 * Phi' ^ n

Let me know if this helps.