Can the Sequence \( a_n \) Satisfy the Inequality \( a_n \leq 20n \)?

[t.kirschner99]

Homework Statement

a₀ = 0, and for n > 0, $$a_n = a_{\frac {n} {5}} + a_{\frac {3n} {5}} + n $$

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

Prove that a_n ≤ 20n

Homework Equations

See above.

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

 

[t.kirschner99]

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

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

 

[SammyS]

Homework Statement

a₀ = 0, and for n > 0, $$a_n = a_{\frac {n} {5}} + a_{\frac {3n} {5}} + n $$

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

Prove that a_n ≤ 20n

Are you sure that this is true?

 

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

 

[Ray Vickson]

Homework Statement

a₀ = 0, and for n > 0, $$a_n = a_{\frac {n} {5}} + a_{\frac {3n} {5}} + n $$

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

Prove that a_n ≤ 20n

Homework Equations

See above.

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

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

 

[haruspex]

assume
$a_k \leq 20k$

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

 

[RUber]

you mean, assume an≤20n ∀ n≤k, right?

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.