In: Advanced Math
If n>=2, prove the number of prime factors of n is less than
2ln n.
Proof by induction.
For , number of prime factors of 2 is , hence the statement is true for n=2.
Assume the statement is true for all i.e. for all , number of prime factors of m is less than .
To prove the statement we need to show number of prime factors of n+1 is less than .
Suppose is prime then note that of prime factors of n+1 is 1, which is less than .
So assume is composite. Let be a prime factor of . Then note that , hence number of prime factore of is less than .
Note that, number of prime factors of = (number of prime factors of )----------------(*)
Now note that for any prime , i.e. .
Thus from (*) we get, .
Hence we proved the number of prime factors of n+1 is less than
Hence done by induction.