# Math Help - recurrance relations

1. ## recurrance relations

Hey my uni lecturer has set a question as follows -

Solve the following recurrance relation:
W(n) = W(n-1) + 3
W(0) = 1

I haven't a baldy what he wants. I think the W mean worst case analysis, but that's all I know about it! Anybody want to give it a go?

2. $\begin{array}{l}
W(0) = 1 \\
W(1) = W(0) + 3 = 4 \\
W(2) = W(1) + 3 = \left[ {W(0) + 3} \right] + 3 = 1 + 2(3) \\
\vdots \\
W(n) = ? \\
\end{array}
$

Do you see the answer?

3. w(n) = w(0) + n*3
??
Cheers Plato

4. Originally Posted by stewpert
w(n) = w(0) + n*3
??
Cheers Plato
Not quite, but you are correct. You should use $w(n) = 1 + 3n$ as your formula, otherwise on it's own you could never find $w(0)$.