Recursive relations

Printable View

• Mar 24th 2010, 03:44 AM
MathZea
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
• Mar 24th 2010, 04:49 AM
emakarov
In a), you almost solved it. You unfolded the definition three times. Generalizing from 3 to \$\displaystyle i\$ we get

\$\displaystyle 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 \$\displaystyle 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 \$\displaystyle a_1=0\$.
• Mar 24th 2010, 09:43 PM
MathZea
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 (Worried).

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

Quote:

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?
• Mar 25th 2010, 07:17 AM
MathZea
Ah sweet, thank you very much! My dad was able to help me with the geometric equation in the end (Nod). No doubt I will be back come the next fortnight *sigh*.

+1 Thanks again