# Solving recurrence systems

• May 14th 2010, 09:59 AM
RedKMan
Solving recurrence systems
Solve the recurrence system below and dtermine a formula for the time complexity function T(n).

T(0) = 4.
T(n) = 5 + T(n - 1) (n > 0)

My effort at solving is below...

T(3) = 5 + T(2).
T(2) = 5 + T(1).
T(1) = 5 + T(0).

T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)
T(3) = 3 * 5 + T(0)
T(3) = 15 + 4.

Now try to obtain a formula for T(n) in terms of n.
T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(1) = 5 + T(0).
T(0) = 4.

T(n) + T(n - 1) + T(1) + T(0) = 3 * 5 + T(n - 1) + T(n - 2) + T(0) + 4.

**THIS IS WHERE MY BRAIN HITS MELTING POINT AND THE COOLANT IS RELEASED.

I'm pretty sure the formula should be T(n) = 5 * n + 4. So,

T(0) = 5 * 0 + 4 = 4
T(3) = 5 * 3 + 4 = 19.

I need to prove it though :(
• May 14th 2010, 10:14 AM
Plato
$\begin{array}{rcl}
{T_4 } & = & {5 + T_3 } \\
{} & = & {5 + \left[ {5 + T_2 } \right]} \\
{} & = & {5 + \left[ {5 + \left[ {5 + T_1 } \right]} \right]} \\
{} & = & {\left( 3 \right)5 + 4} \\ \end{array}$

Now is not clear what the pattern is?
• May 14th 2010, 10:40 AM
Soroban
Hello, RedKMan!

You're making it much too hard . . .

Quote:

Solve the recurrence system and determine a formula for the function $T(n).$.

$T(0) = 4,\quad T(n) \:=\: T(n - 1) + 5, \quad n > 0$

Crank out the first few terms . . .

. . $\begin{array}{c|c}
n & T(n) \\ \hline
0 & 4 \\ 1 & 9 \\ 2 & 14 \\ 3 & 19 \\ 4 & 24 \\ \vdots & \vdots \end{array}$

The sequence starts at 4 and "goes up by 5."

It is clear that the function is: . $T(n) \;=\;4 + 5n$

• May 14th 2010, 01:16 PM
RedKMan
How does this look below:-

Now try to obtain a formula for T(n) in terms of n.

T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(2) = 5 + T(1)
T(1) = 5 + T(0).
T(0) = 4.

Sum each side and equate result...

T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

Subtract terms that appear on both sides...

T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.

I'm a bit dubious about my algebra above, I feel like I'm close, I can taste it. Is it close / correct?
• May 14th 2010, 05:35 PM
Renji Rodrigo
You can do this

$t(k+1)=t(k)+5$
so

$t(k+1)-t(k) =5$

apply the summation $\sum^{n-1}_{k=0}$
on the both sides, the first is a telescoping summation

$\sum^{n-1}_{k=0} t(k+1)-t(k) = t(n)-t(0)=t(n)-4 =\sum^{n-1}_{k=0} 5=5n$
so
$t(n)=5n +4$
• May 14th 2010, 08:28 PM
undefined
Quote:

Originally Posted by RedKMan
I'm pretty sure the formula should be T(n) = 5 * n + 4. So,

T(0) = 5 * 0 + 4 = 4
T(3) = 5 * 3 + 4 = 19.

I need to prove it though :(

Well I would hope that after reading these posts and thinking about them, you will no longer be "pretty sure" but rather 100% sure that the solution is T(n) = 5n + 4.

As for proof, if you're comfortable with inductive proofs, this one is very easy. Using mathematical induction is the typical way to prove these kinds of things.
• May 15th 2010, 01:05 AM
RedKMan
Problem is I need to use algebra to arrive at the formula rather than guessing and then using induction to prove it. Thats why I'm hoping someone can check my,

T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(2) = 5 + T(1)
T(1) = 5 + T(0).
T(0) = 4.

Sum each side and equate result...

T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

Subtract terms that appear on both sides...

T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.

Thus T(n) = 4 + 5n
• May 15th 2010, 01:21 AM
undefined
Quote:

Originally Posted by RedKMan
Problem is I need to use algebra to arrive at the formula rather than guessing and then using induction to prove it.

There is no guessing involved. You can see that the expression is T(n) = 5n + 4 if you just look hard enough.

It's like this sequence:

a(0) = 1
a(n) = 2*a(n-1), n>0

I can just see that this is a(n) = 2^n and there is absolutely no guessing involved.

Although to be fair, guessing is a valid approach for many of these types of problems.

Quote:

Originally Posted by RedKMan
Thats why I'm hoping someone can check my,

T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(2) = 5 + T(1)
T(1) = 5 + T(0).
T(0) = 4.

Sum each side and equate result...

T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

...

Where did this last equation come from??? When I sum each side I get

T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4
• May 15th 2010, 01:42 AM
RedKMan
Your correct, when you sum each side you do get,

T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4

Removing all the terms that appear on both sides, I get,

T(n) + T(2) = 5 + 5 + T(n - 2) + 5 + 5 + 4

Problem is I think I need to get rid of that T(2) term on the right some how??
• May 15th 2010, 01:48 AM
undefined
Quote:

Originally Posted by RedKMan
Your correct, when you sum each side you do get,

T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4

Removing all the terms that appear on both sides, I get,

T(n) + T(2) = 5 + 5 + T(n - 2) + 5 + 5 + 4

Problem is I think I need to get rid of that T(2) term on the right some how??

I could be wrong, but I don't think your approach will succeed.

If you really dislike induction, Renji Rodrigo's post looks like a great option for you.
• May 15th 2010, 06:05 AM
RedKMan
I've gone with induction and it all works out.

With the time complexity function being T(n) = 5n + 4.

I've worked out the Big Oh value to be:-

f(n) = 5n. Giving O(n) of linear type.

Does that look right?

Thanks for all the help everyone.