2
$\begingroup$

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?

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

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$.

$\endgroup$
  • 1
    $\begingroup$ Actually $G_n = n+1$. $\endgroup$ – Yuval Filmus May 11 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.