# Math Help - Recursive relations

1. ## Recursive relations

Hi everyone, i am totally stumped with this section of my coarse work, Maths is not my friend, and my father, who is a maths 1,2 and calculus teacher can't for the life of him work these two out, thus i have resorted to my last ... resort ... ANY help would be greatly appreciated in working out these recursive relations.

a)
an = a(n/2) + n, for n >=2, with a1 = 0
substitute n = 2^k, solve with iteration,

thus,
a2^k = a2^(k-1) + 2^k
= a2^(k-2) + 2^(k-1) + 2^k
=a2^(k-3) + 2^(k-2) + 2^(k-1) + 2^k

Im stumpted here on, not a clue really as all the text book examples and lecturers examples do not follow these patterns.

Also
b)
an = a(n/2) + n^2, for n >=2, with a1 = 0

Not a clue ...

Due tomorrow so im cutting it close, otherwise its a slap on submit job. (no there were 30 other questions i've done this isn't a last minute job, last 2 questions.)

Thank you!!
Mathzea

2. In a), you almost solved it. You unfolded the definition three times. Generalizing from 3 to $i$ we get

$a_{2^k}=a_{2^{k-i}}+2^{k-i+1}+2^{k-i+2}+\dots+2^{k-1}+2^{k}$

What is the limit case? Rewrite this formula when $i=k-1$. This can be summed up using the formula for the sum of geometric progression. Be careful with the second term, which follows $a_1=0$.

3. OH i see what you've done there, however the only information we are given is:

for n >= 2, with a1 = 0, when n is a power of 2.

What do you mean by the 'limit case'

Thank you for the reply I'm still a bit lost on the following steps of solving the geometric expression .

Mathzea.

4. "Limit case" is not an official term; I meant what happens when, in the right-hand side of the equation above, you cannot unfold $a_{2^{k-i}}$ according to the definition $a_n = a_{n/2} + n$. This happens when $a_{2^{k-i}}=a_1$, i.e., $2^{k-i}=1$, i.e., $k-i=0$. Actually, I was wrong earlier when I suggested considering $i=k-1$. The limit case happens when $i=k$.

I'm still a bit lost on the following steps of solving the geometric expression
The sum of geometric progression is a standard topic that must be described, in particular, in your textbook. Maybe you can search "Pre-Algebra and Algebra" section of this forum or ask a question there?

5. Ah sweet, thank you very much! My dad was able to help me with the geometric equation in the end . No doubt I will be back come the next fortnight *sigh*.

+1 Thanks again