Strong Induction for a sequence inequality?

Question

On the previous midterm, there was a question that I couldn't solve. It gave us this sequence

The sequence $$a_0, a_1, a_2,... $$is defined by $$a_0 = 1,$$ and for all integers $$n > 0,$$ $$a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor 2n/3 \rfloor} + n. $$

Prove by Strong Induction that $a_n >4n$ for all integers $n>a$. where a is the integer you chose in part (b).

I got to the part where I figured out that the lowest integer that could be used was 3, but I didn't know how to prove by strong induction, as I had forgotten the difference between regular induction and strong induction.

Would 3 be the basis of our proof? If so? What would the inductive step look like?

Answer 1

$$a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor 2n/3 \rfloor} + n $$

$$\forall n > m ~~ a_n > 4n $$

(a) Inductive case: $$ a_n > 4n $$ $$a_{\lfloor n/2 \rfloor} + a_{\lfloor 2n/3 \rfloor} + n > 4n $$

The inductive assumptions that you will need are $a_{\lfloor n/2 \rfloor} > 4{\lfloor n/2 \rfloor}$ and $a_{\lfloor 2n/3 \rfloor} > 4 {\lfloor 2n/3 \rfloor}$. Using the principle that $x > y \text{ and } y > z \text{ implies } x > z$, you apply the inductive assumptions:

$$4{\lfloor n/2 \rfloor} + 4{\lfloor 2n/3 \rfloor} + n > 4n $$

Now I would recommend using $\lfloor a / b \rfloor b + a {~\rm mod~} b = a$ to get:

$$4\frac{n - n{~\rm mod~} 2}{2} + 4\frac{2n - 2n{~\rm mod~} 3}{3} + n > 4n$$

and simplify fractions:

$$2n - 2(n{~\rm mod~} 2) + \frac 83 n - \frac43 (2n{~\rm mod~} 3)+ n > 4n$$

$$2(n{~\rm mod~} 2) + \frac43 (2n{~\rm mod~} 3) < \left(1 + \frac 23\right)n$$

And since the left hand side is finite, it must eventually (for $n>m$) be less than the right hand side.

(b) Find an $m$

The ${\rm mod~}2$ and ${\rm mod~}3$ from the last equation of the last part means that once you find an $n_0$ for which the relation is true, it must be true for $n > n_0 + 6 = m$

$a_0 = 1$, so the statement must be true for all $n > 0+6$, although by checking cases $n \in \{1 \dots 5\}$ you can see it is true for $n > 1$.

Answer 2

You can check that $$\left\lfloor\frac{n}2\right\rfloor\ge\frac{n-1}2\qquad\text{and}\qquad\left\lfloor\frac{2n}3\right\rfloor\ge\frac{2n-2}3$$ for all $n$. If $\frac{1}2(n-1)$ and $\frac{1}3(2n-2)$ are both at least $3$, your induction hypothesis tells you that

$$a_{\lfloor n/2\rfloor}>4\cdot\frac{n-1}2=2n-2$$

and

$$a_{\lfloor 2n/3\rfloor}>4\cdot\frac{2n-2}3=\frac{8}3n-\frac{8}3\;.$$

Add those and $n$, and you find that

$$a_{\lfloor n/2\rfloor}+a_{\lfloor 2n/3\rfloor}+n>\frac{17}3n-\frac{14}3\;.$$

This is good enough provided that

$$\frac{5}3n-\frac{14}3\ge 0\;,$$

or $5n\ge 14$. In particular, it holds for all $n\ge 3$. However, you need $n\ge 7$ to ensure that $\frac{1}2(n-1)\ge 3$ and $\frac{1}3(2n-2)\ge 3$, so your basis step in this approach has to be to check by hand lthat the result holds for $n=3,4,5,6$.