1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @Regret sorry I just added more info, 'where a is the integer you chose in part (b)." $\endgroup$ – edkrs Mar 6 '15 at 8:09
  • 2
    $\begingroup$ @edkrs Which part (b)? also check out math.stackexchange.com/questions/517440/… for information on strong induction. $\endgroup$ – DRF Mar 6 '15 at 8:16
  • $\begingroup$ @DRF: It doesn't matter: $a$ is pretty clearly supposed to be the smallest integer making the statement true. $\endgroup$ – Brian M. Scott Mar 6 '15 at 8:20
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you go from a_⌊n/2⌋+a_⌊2n/3⌋+n>(17/3)n−(14/3). to 5/3n - 14/3 >= 0? $\endgroup$ – edkrs Mar 6 '15 at 20:00
  • 1
    $\begingroup$ @edkrs: You want $$a_{\lfloor n/2\rfloor}+a_{\lfloor 2n/3\rfloor}+n>4n=\frac{12}3n\;,$$ and $$\frac{17}3n-\frac{14}3=\frac{12}3n+\left(\frac53n-\frac{14}3\right)\;,$$ so the first inequality holds if and only if $\frac53n-\frac{14}3\ge 0$. $\endgroup$ – Brian M. Scott Mar 6 '15 at 20:04

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.