How to prove a bound function for a sequence of numbers? Let $G_n$ be defined by

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

How can I prove that $f(n) = n$ is a bound function (or loop variant) for the above sequence?
If you have tried, you will find that 
$$\begin{aligned}
G_5&amp;=6\\
G_6&amp;=7\\
G_7&amp;=8\\
G_8&amp;=9\\
G_9&amp;=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$.