Strong Induction for a sequence inequality? 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?
 A: $$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$.
A: 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$.
