Math 2.0

statement proposition

Exponentials dominate powers in sequences

Statement

Let kk be a natural number and let rr be a real number with r>1r > 1. Then lim⁡n→∞nkrn=0.\lim_{n \to \infty} \frac{n^k}{r^n} = 0.

Remarks

For k=1k = 1 and r=2r = 2, it says n/2n→0n / 2^n \to 0. The terms are 1/2,2/4,3/8,4/16,…1/2, 2/4, 3/8, 4/16, \dots. One proof uses the ratio of consecutive terms. The ratio (n+1)knk⋅1r\frac{(n+1)^k}{n^k} \cdot \frac{1}{r} tends to 1/r<11/r < 1, so the terms eventually shrink by a fixed factor. In the language of little o notation, it says nk=o(rn)n^k = o(r^n). The node exponential growth beats polynomial growth gives the version for real variables.

Explanations

L1 human

A power such as n10n^{10} grows fast, but an exponential such as 1.01n1.01^n grows faster in the end. For small nn the power can be much larger. For large nn the exponential always wins.

What this node needs for W1
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 7 nodes in this order. The foundations come first, and the list ends with this node.

Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Sequence definition
  2. Real sequence definition
  3. Geometric sequence definition
  4. Limit of a sequence definition
  5. Sequence tending to infinity definition
  6. The sequence r^n tends to infinity for r > 1 example
  7. Exponentials dominate powers in sequences statement

Sources

  1. Web https://en.wikipedia.org/wiki/Big_O_notation, Exponentials dominate powers