Sunday, March 6, 2022

Biggest k such that n over k is less than or equal to n!

Let's find the biggest k such that $n^k \le n! $

In an introductory class for the induction method, one of the common examples given by the teachers is "prove that $n^n \ge n!$". This problem is intuitive since both of the sides are calculated doing n different multiplications while in $n!$ the multipliers are generally less than n. 

While the teacher was proving this in the whiteboard, I came up with a simple question: What is the biggest possible value for k such that $n^k \le n! $. At first I wanted k and n to be an integers but the question can be solved in a similar manner if k is a positive real number. You should try to solve it on your own but here's my solution:

Take the logarithm of both sides with your favorite base:

\[\ln{n^k} \le \ln{n!} \]

\[k \, \ln{n} \le \ln{n} +\ln{n-1}+....+ \ln{2} + \ln{1} \]

\[ k \le \frac{ \ln{n} +\ln{n-1}+....+ \ln{2} + \ln{1} }{\ln{n}} \]

Round k to the biggest possible integer such that this holds.

As you can see when we plot the numbers it's a pretty linear graph but when we look at the ratio between n and k the graph changes:

And when we look at the limit using wolframalpha, just like you can see from the graph, n/k converges to 1.

You can find this sequence in OEIS with the code number A039960.

 

1 comment:

  1. I just need to say this is a well-informed article which you have shared here about hoodies. It is an engaging and gainful article for us. Continue imparting this sort of info, Thanks to you. German Language Lesson Online

    ReplyDelete

Game Idea: Blobtopia

Blobtopia Project Announcement Blobtopia: A Journey in Coding Joy Lately, I’ve had a revelation: school and work h...