Alex wrote:
Can I ask for a quick additional hint since the last one really helped?
It would be better to create a new sci.math thread.
Suppose that a sequence is defined by the following recurrence
relation:
a_{n}=a_{n-1} + a_{n-2} + a_{n-3}
and you are given some initial values a_{0}, a_{1} and a_{2}
Also suppose that a recursive algorithm uses the recurrence relation
three times to evaluate a_{n-1}, a_{n-2} and a_{n-3} and then adds the
resulting values to obtain a_{n}.
Would it be possible to have a hint as to how I would show that the
total number of times t_{i} that a_{n-i} is evaluated satisfies:
t_{i}=t_{i-1} + t_{i-2} + t_{i-3}
with t_{0}=t_{1}=1 and t_{2}=2.
Hint: use induction.
Best regards,
Jose Carlos Santos
|