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$ – John L. May 11 '19 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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually $G_n = n+1$. $\endgroup$ – Yuval Filmus May 11 '19 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.