Find monotonicity of a formula

[Mondo]

Hello,

I need to find the maximum of a function $$k_n = \frac{100!n}{(100-n)! \cdot 100^{n+1}}$$By quick empirical test I found out that it is increasing for few first n. So my first intuition was "what is the last increasing n" which I wrote as an inequality $$k_{n} > k_{n+1}$$but unfortunately I was unable to solve it -> I got to the point $$-100n^2 + 9999n + 99 > 0$$ which just doesn't give sane solution. However if I turn my inequality to $$k_{n+1} > k_{n}$$ I get correct solution which is 9. So why does the first inequality fail to deliver the solution and what other methods could I use?

 

[Dr.Peterson]

Hello,

I need to find the maximum of a function $$k_n = \frac{100!n}{(100-n)! \cdot 100^{n+1}}$$By quick empirical test I found out that it is increasing for few first n. So my first intuition was "what is the last increasing n" which I wrote as an inequality $$k_{n} > k_{n+1}$$but unfortunately I was unable to solve it -> I got to the point $$-100n^2 + 9999n + 99 > 0$$ which just doesn't give sane solution. However if I turn my inequality to $$k_{n+1} > k_{n}$$ I get correct solution which is 9. So why does the first inequality fail to deliver the solution and what other methods could I use?

Please show the details of your work. It makes no sense that you would get different values of n just by reversing the inequality, which only changes signs. And I don't get the quadratic inequality you show.

And the turning point is about 9.5, which you're rounding, right?

 

[Mondo]

Ok so I it looks I did a stupid mistake when substituting (n+1) - instead of (100 - (n+1))! I did (100 - n + 1)! and hence I was unable to solve it.

And the turning point is about 9.5, which you're rounding, right?

Yes the turning point is about 9.5. Here I made another mistake - since each $$k_n$$ is a natural number it is obvious that 10th element will be larger than the 9th. On the other hand 11th element is the first decreasing one.

 

[Dr.Peterson]

Ok so I it looks I did a stupid mistake when substituting (n+1) - instead of (100 - (n+1))! I did (100 - n + 1)! and hence I was unable to solve it.


Yes the turning point is about 9.5. Here I made another mistake - since each $$k_n$$ is a natural number it is obvious that 10th element will be larger than the 9th. On the other hand 11th element is the first decreasing one.

I assume you meant that each n is a natural number.

Yes, your inequality, done correctly, shows that $k_{n+1}<k_n$ when $n>9.5$, so that the first time it decreases is from 10 to 11.

 

[Mondo]

One thing that still bothers me a bit is the inequality itself - for $$k_{n+1} > k_{n}$$ we say "let's find the last n for which the value is bigger than the preceding term" but this inequality is satisfied even for n = 1 as $$k_2 > k_1$$. So why are we sure this inequality will yield "the last n" instead of any other n that satisfies it?

 

[Dr.Peterson]

One thing that still bothers me a bit is the inequality itself - for $$k_{n+1} > k_{n}$$ we say "let's find the last n for which the value is bigger than the preceding term" but this inequality is satisfied even for n = 1 as $$k_2 > k_1$$. So why are we sure this inequality will yield "the last n" instead of any other n that satisfies it?

Quick answer: It does both!

But please show your actual work: What was the correct inequality you found, and what was your solution for it? That will give us something specific to discuss.

The solution you should have found will be an interval. The greatest integer in that interval will be what you are looking for. That's how you turn the solution to the inequality into the answer to your question.

The lower limit of that interval turns out to be negative, so any n up to and including 9 will be in it. I assume you aren't surprised that this sequence starts out increasing, and eventually decreases; the latter point is what you're looking for. Here's a graph:

 

[Mondo]

Ok so here is my solution to inequality $$\frac{100!n}{(100-n)! \cdot 100^{n+1}} > \frac{100!(n+1)}{(100-(n+1))! \cdot 100^{n+2}}$$I divide by $$100!$$ and multiply by $$(100 - n)! \cdot 100^{n+1}$$ to get $$n > \frac{(100 - n)(n+1)}{100}$$ after simplification $$100n > 100n + 100 - n^2 - n$$ $$n^2 + n - 100 > 0$$ solving quadratic equation $$\delta = 401, \sqrt{\delta} = 20.02, n_1 = negative, n_2 = 9.5$$Now is the time to draw a conclusion - I started with $$k_n > k_{n+1}$$ and what makes me sure that the solution is a range from $$[0 - 9.5]$$ instead of a single $$n = 9.5$$?

Also, since we look for the natural number n and our solution is a fractional number 9.5 we concluded the sequence is increasing up to 10th element but can we really say so? In fact we know that it is still increasing after 9 but not all the way up to 10! So I can imagine it could be that it is increasing from from 9 to 9.5 but then starts to decrease so by the time we are at 10 we have a lower value than we had at 9?! That said I think with the solution 9.5 in hand we can not conclude it is increasing up to 10 - instead we should really make a test plugging n = 9 and n = 10 into the formula. Do you agree?

 

[Dr.Peterson]

Also, since we look for the natural number n and our solution is a fractional number 9.5 we concluded the sequence is increasing up to 10th element but can we really say so? In fact we know that it is still increasing after 9 but not all the way up to 10! So I can imagine it could be that it is increasing from from 9 to 9.5 but then starts to decrease so by the time we are at 10 we have a lower value than we had at 9?! That said I think with the solution 9.5 in hand we can not conclude it is increasing up to 10 - instead we should really make a test plugging n = 9 and n = 10 into the formula. Do you agree?

Such a check is always a good thing to do, but it is not required here.

The solution to the inequality is an interval, not a single number; it implies that for integers n = 0, 1, 2, ..., 9, $k_{n+1}>k_n$, but for k = 10, 11, ..., $k_{n+1}<k_n$. In particular, $k_{10}>k_9$ but $k_{11}<k_{10}$. So we know that without needing to check (as long as we trust our work -- I made a mistake my first time through, which was why I made the graph!).

The expression is defined only for non-negative integers n (unless you extend the definition of factorial), so you can't really talk about what it is doing between 9 and 10. In particular, the inequality doesn't give the sign of a derivative, but the slope of a secant, from n to n+1; it is not about how the function is changing at a single point.

All of this makes this a very interesting problem, and what you did a very good method of solution -- but easy to misunderstand!

 

[Mondo]

The expression is defined only for non-negative integers n

Hmm I would say it is defined for n in range [1-99]. The negative n would not make the factorial negative, only n greater or equal to 100 would do.

In particular, the inequality doesn't give the sign of a derivative, but the slope of a secant, from n to n+1;

I am curious why did you brought the sign of a derivative here? Is that to show the difference with the other method of finding the maximum, namely the method of finding the derivative?

 

[Dr.Peterson]

Hmm I would say it is defined for n in range [1-99].

True; but I wasn't trying to state the domain fully. What I said was in contrast to letting n be 9.5, not 101. You seem to have missed the point.

I am curious why did you brought the sign of a derivative here? Is that to show the difference with the other method of finding the maximum, namely the method of finding the derivative?

Well, you can't find the derivative, because the function is only defined for integers; that was my point. That is, you can't say, as you did:

In fact we know that it is still increasing after 9 but not all the way up to 10! So I can imagine it could be that it is increasing from from 9 to 9.5 but then starts to decrease so by the time we are at 10 we have a lower value than we had at 9?!

If it were a continuous function, you could say that sort of thing, and talking about whether it is increasing would be talking about the sign of the derivative.

But you aren't talking about that, and you can't be!

What you did was to find, in effect, the change in y when x increases from one integer to the next. This is the discrete analogue of the derivative.