Lesson 2

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(2, 13)
plt.plot(n, n ** 3, label='$n^3$')
plt.plot(n, 2 ** n, label='$2^n$')
plt.legend()
plt.savefig('polyexp.png')

The graph shows that \(2^{n}\) starts to surpass \(n^{3}\) right around \(n=10\). As \(n\) grows, the first function will move further away from the second, and this will be evident in our proof of the inequality. Below, we prove that \(2^{n} \ge n^{3}\), for all integers \(n \ge 10\), by induction on \(n\).

• Base \(n=10\).  It is directly verified: \(1024 > 1000\).


• Step \(n \to n+1\).  When transitioning from \(n\) to \(n+1\), the left part is multiplied by two, whereas the right part is multiplied by \[\frac{(n+1)^3}{n^3}=\left(1+\frac{1}{n} \right)^{3} \ .\] For \(n \ge 10\), this number is no more than \(1.1^{3} < 2\).