Recurrence relation problem

Hi All. I usually solve recurrence relations but I'm struggling with this one. I need to find the general term.

$\displaystyle A(n)= c n + A(\lfloor n/2 \rfloor)$ for $\displaystyle n > 2,$ $\displaystyle A(n) = 1$ for$\displaystyle n = 2$ where $\displaystyle c$-constant

Thanks

Re: Recurrence relation problem

It's usually helpful to just calculate the first few values to "see" what's happening in a recurrence. What follows doesn't solve it, but might prove helpful.

A(2) = 1.

A(3) = 3c + A(floor(3/2)) = 3c + A(1). Uh-oh, A(1) isn't defined.

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

A(5) = 5c + A(floor(5/2)) = 5c+A(2) = 5c+1.

A(6) = 6c + A(3) = 6c+(3c+A(1)) = 9c + A(1).

A(7) = 7c + A(floor(7/2)) = 7c+A(3) = 7c + (3c+A(1)) = 10c + A(1).

A(8) = 8c + A(4) = 8c+ (4c+1) = 12c + 1.

A(9) = 9c + A(floor(9/2)) = 9c+A(4) = 9c + (4c+1) = 13c + 1.

A(10) = 10c + A(5) = 10c+(5c+1) = 15c + 1.

A(11) = 11c + A(floor(11/2)) = 11c+A(5) = 11c + (5c+1) = 16c + 1.

A(12) = 12c + A(6) = 12c+(9c + A(1)) = 21c + A(1).

A(13) = 13c + A(floor(13/2)) = 13c+A(6) = 13c + (9c + A(1)) = 22c + A(1).

A(14) = 14c + A(7) = 14c+ (10c + A(1)) = 24c + A(1).

A(15) = 15c + A(floor(15/2)) = 15c+A(7) = 15c + (10c + A(1)) = 25c + A(1).

A(16) = 16c + A(8) = 16c+ (12c + 1) = 28c + 1.

A(17) = 17c + A(floor(17/2)) = 17c+A(8) = 17c + (12c + 1) = 29c + 1.

What becomes clear from that?

First: A(1) is left undefined.

Second: for n>=4, we need only consider even values n = 2k, since A(2k+1) = A(2k) + c.

Third: Look for patterns (and then try to prove inductively):

n = 4, c-coeff = 4 (perhaps exludable as an "initial" value?)

n = 6, c-coeff = 9

n = 8, c-coeff = 12 (+3 from last)

n = 10, c-coeff = 15 (+3 from last)

n = 12, c-coeff = 21 (+6 from last)

n = 14, c-coeff = 24 (+3 from last)

n = 16, c-coeff = 28 (+4 from last)

The pattern is unclear. Finding it is what remains of the problem.

Constant term is +1 except at n even being = 6, 12, and 14, where it's +A(1).

Note how n=6 was +A(1), so n=7 was +A(1) also. That's 2 consecutive +A(1). But that led to n = 12 and n=14 being +A(1), so 4 consecutive +A(1) (n = 12, 13, 14, 15).

Since n = 12, 13, 14, 15 are all +A(1), will have +A(1) later for n=24, 25, 26, 27, 28, 29, 30, and 31. So those 4 consecutive +A(1) leads to the next batch of +A(1)'s being 8 consecutive.

The pattern for the constant term should appears clear and calcuable.