# How to prove a bound function for a sequence of numbers?

Let $$G_n$$ be defined by

$$G_n = \begin{cases} 1 & n=0 \\ 2 & n = 1 \\ 3 & n = 2 \\ 4 & n = 3 \\ 2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4 \end{cases}$$

How can I prove that $$f(n) = n$$ is a bound function (or loop variant) for the above sequence?

• Have you tried computing $G_5$? $G_6$? $G_7$ $G_8$? $G_9$? What can you observe? – Apass.Jack May 11 at 1:44

If you have tried, you will find that \begin{aligned} G_5&=6\\ G_6&=7\\ G_7&=8\\ G_8&=9\\ G_9&=10.\\ \end{aligned}
By now, you should have probably guessed that $$G_{n}=n+1$$. Now you can try proving it, using induction on $$n$$.
Once that formula has been proved, $$f(n)=n$$ is of course a lower bound for $$G_n$$.
• Actually $G_n = n+1$. – Yuval Filmus May 11 at 12:34