# Induction Inequality Question

Tags:
1. Aug 2, 2017

### t.kirschner99

1. The problem statement, all variables and given/known data
a0 = 0, and for n > 0, $$a_n = a_{\frac {n} {5}} + a_{\frac {3n} {5}} + n$$

For the above equation, besides an, the subscripts are floored

Prove that an ≤ 20n
2. Relevant equations

See above.

3. The attempt at a solution

I know how to do the question, my problem is starting it. It's strong induction vs. induction. I am leaning towards strong induction due to the first equation having multiple conditions. I would assume that my base case then would be n=0 and n=1

2. Aug 3, 2017

### t.kirschner99

Cannot edit my solution attempt, ignore what I put there.

3. The attempt at a solution

Questioning myself on strong induction, but I committed to it.

Base case of 0 and 1 are good.

Inductive Hypothesis: $$a_k \leq 20k$$

Proof:

Want to prove $$a_{k+1} \leq 20(k+1)$$

$$a_{k+1} = a_{\frac {k+1} {5}} + a_{\frac {3k+3} {5}}+ k + 1$$

I am getting stuck at this point, don't really know where to go from here. The floors of the subscripts are what is confusing me

Last edited: Aug 3, 2017
3. Aug 3, 2017

### SammyS

Staff Emeritus
Are you sure that this is true?

4. Aug 3, 2017

### RUber

I recommend you look at it this way:
$a_k = a_{\left\lfloor \frac{k}{5} \right\rfloor} +a_{\left\lfloor \frac{3k}{5} \right\rfloor} + k$
assume
$a_k \leq 20k$
Then show that
$a_{k+1} \leq a_k + 20 \leq 20(k+1).$

5. Aug 3, 2017

### Ray Vickson

Hint: besides the suggestion in #4, you should remember that $\lfloor x/5 \rfloor$ increases by 1 when $x$ passes through integers of the form $5n$ and $\lfloor 3x/5 \rfloor$ increses by 1 when $x$ passes through integers of the form $5n/3$.

6. Aug 3, 2017

### haruspex

you mean, assume an≤20n ∀ n≤k, right?
(Seems to me the factor 20 specified is unnecessarily large. It could have been set at 5.)

7. Aug 4, 2017

### RUber

That's exactly what I meant. It has to be true for all the terms up to and including the current one, then you can inductively prove it for the next one $a_{k+1}$.

If the floor function is confusing, sometimes you can just get rid of it.
Remember that the floor function is always less than what is applied to.
$\lfloor 12/5 \rfloor \leq 12/5$
So if $a_n \leq 20n \forall n\leq k$, then you can say that $a_{k/5} \leq 20(k/5)$ dropping the floor part out.

In doing this, although not the most refined technique, you can eliminate what was confusing you. Then you have an algebraic proof. You will end up needing to satisfy some condition for a minimum number that k has to be greater than. Smaller terms you can demonstrate explicitly.