Re: Prove that an irrational number has an infinite base q expansion

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
.

Quantcast