Day 8 — Exponents & logarithms

Updated

July 30, 2026

Day 8 — Exponents & logarithms

Stage I · concept day
Goal: Prove and apply exponent laws for integer exponents; work with roots; define logarithms; use change of base; connect \(\log_2\) to bits and information; solve simple exponential equations.

Why this matters

Complexity is full of \(n^2\), \(2^n\), and \(\log n\). Bit length of an integer \(n\) is about \(\lfloor\log_2 n\rfloor+1\). Cryptography and hashing talk about “bits of security.” Exponent and log laws are algebraic muscle for Stage II growth and Stage VIII asymptotics.

Theory

Integer exponents

For \(a\neq 0\) and \(n\in\mathbb{Z}_{\ge 0}\): \[a^0=1,\qquad a^{n+1}=a^n\cdot a.\] For \(n>0\), \(a^{-n}=\frac{1}{a^n}\) (when working in \(\mathbb{Q}\) or \(\mathbb{R}\)).
\(0^n=0\) for \(n>0\); \(0^0\) left undefined.

Exponent laws (with proofs for integer exponents)

Assume \(a,b\neq 0\) and \(m,n\in\mathbb{Z}\) (with denominators defined).

Law 1. \(a^m a^n=a^{m+n}\).

Proof idea (nonnegative \(m,n\)). Fix \(m\); induct on \(n\). Base \(n=0\): \(a^m\cdot 1=a^m=a^{m+0}\). Inductive: \(a^m a^{n+1}=a^m a^n a=a^{m+n}a=a^{m+n+1}\). Extend to negatives using \(a^{-k}=1/a^k\). \(\square\)

Law 2. \((a^m)^n=a^{mn}\).

Proof idea. \((a^m)^n=a^m\cdot a^m\cdots a^m\) (\(n\) times) \(=a^{m+\cdots+m}=a^{mn}\) for \(n>0\); similar care for signs. \(\square\)

Law 3. \((ab)^n=a^n b^n\).

Proof idea. Induct on \(n\ge 0\): \((ab)^{n+1}=(ab)^n(ab)=a^n b^n a b=a^{n+1}b^{n+1}\). \(\square\)

Law 4. \(\frac{a^m}{a^n}=a^{m-n}\).

From Law 1: \(a^m=a^{m-n}a^n\).

Non-laws (pitfalls): \((a+b)^n\neq a^n+b^n\) in general; \(a^{b^c}\neq (a^b)^c\) in general.

Roots

For \(a\ge 0\) and integer \(k\ge 2\), \(\sqrt[k]{a}=a^{1/k}\) is the nonnegative \(x\) with \(x^k=a\) (principal root).
\(\sqrt{a^2}=|a|\) for real \(a\).
For odd \(k\), real \(k\)-th roots of negatives exist: \(\sqrt[3]{-8}=-2\).

Laws (principal roots, careful domains): \[\sqrt[k]{ab}=\sqrt[k]{a}\sqrt[k]{b}\quad(a,b\ge 0),\qquad \bigl(\sqrt[k]{a}\bigr)^m=\sqrt[k]{a^m}.\]

Logarithms

For base \(b>0\), \(b\neq 1\), and \(x>0\): \[\log_b x = y \quad\Longleftrightarrow\quad b^y=x.\]

Special bases: \(\log_{10}\) (common), \(\ln=\log_e\) (natural), \(\log_2\) (binary, CS).

Domain: argument \(x>0\); base \(b>0\), \(b\neq 1\).

Log laws

For valid \(x,y>0\) and allowed bases:

  1. \(\log_b(xy)=\log_b x+\log_b y\)
  2. \(\log_b(x/y)=\log_b x-\log_b y\)
  3. \(\log_b(x^r)=r\log_b x\)
  4. \(\log_b b=1\), \(\log_b 1=0\)
  5. \(b^{\log_b x}=x\), \(\log_b(b^y)=y\)

Proof of (1). Let \(\log_b x=m\), \(\log_b y=n\), so \(b^m=x\), \(b^n=y\). Then \(xy=b^m b^n=b^{m+n}\), hence \(\log_b(xy)=m+n\). \(\square\)

Proof of (3). \(x^r=(b^{\log_b x})^r=b^{r\log_b x}\). \(\square\)

Change of base

\[\log_b x=\frac{\log_k x}{\log_k b}\] for any valid base \(k\).

Proof. Let \(y=\log_b x\), so \(b^y=x\). Take \(\log_k\): \(y\log_k b=\log_k x\). \(\square\)

Useful: \(\log_b a=1/\log_a b\).

\(\log_2\) and bits / information

  • Number of bits needed to represent integers \(0..N-1\) is \(\lceil\log_2 N\rceil\) for \(N\ge 1\) (with \(N=1\) meaning \(1\) value needs \(0\) or \(1\) bits depending on convention—usually \(\lceil\log_2 N\rceil\) for \(N\ge 2\)).
  • Bit length of positive integer \(n\): \(\lfloor\log_2 n\rfloor+1\).
  • Each fair binary question halves the search space → information scale is \(\log_2\) of number of alternatives.

Solving simple exponential equations

If \(b^u=b^v\) and \(b>0\), \(b\neq 1\), then \(u=v\).
If \(b^x=c\) with \(c>0\), then \(x=\log_b c\).
Rewrite same bases: \(4^x=(2^2)^x=2^{2x}\).
Example: \(2^{x}=32\Rightarrow x=5\).
\(9^x=27\): \((3^2)^x=3^{2x}\), \(27=3^3\), so \(2x=3\), \(x=\frac{3}{2}\).

Worked examples

Example 1 — Product law

\(2^5\cdot 2^3=2^8=256\). Not \(2^{15}\).

Example 2 — Power of power

\((2^5)^3=2^{15}=32768\).
\(2^{(5^3)}=2^{125}\) enormous—parentheses matter.

Example 3 — Negative exponents

\(3^{-2}=\frac{1}{9}\). \(2^{-3}\cdot 2^{5}=2^{2}=4\).

Example 4 — Root

\(\sqrt{50}=\sqrt{25\cdot 2}=5\sqrt{2}\). \(\sqrt[3]{-27}=-3\).

Example 5 — Log definition

\(\log_2 32=5\) because \(2^5=32\).
\(\log_5 1=0\). \(\log_7 7=1\).

Example 6 — Log product

\(\log_2(8\cdot 4)=\log_2 8+\log_2 4=3+2=5=\log_2 32\).

Example 7 — Change of base

\(\log_8 2=\frac{\log_2 2}{\log_2 8}=\frac{1}{3}\). Check: \(8^{1/3}=2\).

Example 8 — Bits for IDs

Values \(0..999\): need \(\lceil\log_2 1000\rceil=\lceil 9.96\rceil=10\) bits.

Example 9 — Bit length

\(n=1000\): \(\lfloor\log_2 1000\rfloor+1=\lfloor 9.96\rfloor+1=10\) bits for binary representation of \(1000\).

Example 10 — Solve

\(3^{2x}=81=3^4\Rightarrow 2x=4\Rightarrow x=2\).
\(2^{x+1}=2^{3x-5}\Rightarrow x+1=3x-5\Rightarrow 6=2x\Rightarrow x=3\).

Example 11 — Different bases

\(4^{x}=8^{x-1}\): $ (22)x=(23){x-1}2x=3x-3x=3$.

Example 12 — Log equation

\(\log_2(x-1)=3\Rightarrow x-1=8\Rightarrow x=9\) (check domain \(x>1\)).

Example 13 — Information

Dictionary of \(2^{20}\) words: about \(20\) fair yes/no questions in binary search idealization.

Example 14 — Identity

\(\log_b(b^k)=k\); \(b^{\log_b 5}=5\).

Exercises

Easy

  1. Simplify \(5^2\cdot 5^4\) and \((5^2)^4\).
  2. Evaluate \(2^{-4}\), \(10^{0}\), \(7^{1}\).
  3. Find \(\log_2 64\), \(\log_3 81\), \(\log_{10} 1000\).
  4. Simplify \(\log_5(25\cdot 125)\).
  5. Solve \(2^x=128\).

Medium

  1. Prove \(a^m a^n=a^{m+n}\) for nonnegative integers by induction on \(n\).
  2. Simplify \(\frac{a^{6}b^{-2}}{a^{2}b^{3}}\) for \(a,b\neq 0\).
  3. Express \(\log_9 27\) as a rational number.
  4. Use change of base to write \(\log_6 10\) in terms of \(\ln\) or \(\log_{10}\).
  5. How many bits to distinguish \(5000\) user IDs (\(0..4999\))?
  6. Solve \(9^{x}=27^{x-1}\).
  7. Solve \(\log_3(2x+1)=2\).
  8. Simplify \(\sqrt{18}+\sqrt{8}\) if possible.

Hard / proof

  1. Prove \(\log_b(xy)=\log_b x+\log_b y\) from the definition.
  2. Prove the change-of-base formula.
  3. Prove \((ab)^n=a^n b^n\) for \(n\in\mathbb{Z}_{\ge 0}\) by induction.
  4. Show \(\log_b a\cdot\log_a c=\log_b c\) (chain rule for logs).
  5. If \(2^{x}=5\), express \(4^{x}\) and \(2^{x+3}\) without solving for \(x\) first.
  6. Domain: for which real \(x\) is \(\log_2(x^2-1)\) defined?
  7. Disprove \((a+b)^2=a^2+b^2\) with a counterexample; expand correctly.

Challenge / CS-flavored

  1. Password space: \(62\) character alphabet, length \(8\): express size as \(62^8\); estimate \(\log_2(62^8)=8\log_2 62\).
  2. Why is binary search \(O(\log n)\) related to \(\log_2 n\) halvings?
  3. Floating point idea: numbers near \(2^{e}\) — connect exponent field to powers of two (preview Day 9).
  4. Solve \(2^{2x}-2^{x}-2=0\) with \(y=2^{x}\).
  5. Compare growth: for large \(n\), is \(n^{100}\) or \(2^{n}\) larger? (qualitative; Stage VIII formalizes)

Exponential and log graphs (qualitative)

For \(b>1\): \(y=b^{x}\) passes through \((0,1)\), increases, asymptotic to positive \(x\)-axis as \(x\to-\infty\).
\(y=\log_b x\) passes through \((1,0)\), increases slowly, domain \(x>0\), inverse graph reflected across \(y=x\).

Change-of-base computations

\(\log_2 10=\frac{\ln 10}{\ln 2}\approx\frac{2.302}{0.693}\approx 3.32\).
Thus \(10^{d}\approx 2^{3.32 d}\)—bits vs decimal digits: about \(3.32\) bits per decimal digit.

Solving strategies checklist

  1. Same base → equate exponents.
  2. Write both sides as powers of a common base.
  3. Take \(\log\) of both sides (arguments positive).
  4. Substitution \(u=b^{x}\) for equations in \(b^{x}\) and \(b^{2x}\).
  5. Check domain after solving log equations.

Growth comparisons (pre-asymptotics)

For large \(n\): \(2^{n}\) grows faster than \(n^{100}\); \(\log n\) grows slower than any positive power \(n^{\varepsilon}\). Tables for small \(n\) can mislead—always check large \(n\).

Extra exercises

  1. Prove \(\log_b(x/y)=\log_b x-\log_b y\).
  2. Solve \(5^{2x}-5^{x}-6=0\).
  3. Express \(\log_6 72\) as \(a+b\log_6 2\) or similar with integers \(a,b\).
  4. How many bits to store an integer up to \(10^{18}\) (unsigned)?
  5. Show \(\log_2(6^{n})=n\log_2 6\) and estimate using \(\log_2 6=1+\log_2 3\).

CS connection

\(\log_2 n\) counts halvings and tree height for balanced binary trees. Bit complexity of \(n\) is \(\Theta(\log n)\). Exponentiation \(a^n\) by squaring uses \(O(\log n)\) multiplications. Exponential equations model doubling processes (Day 20). Never confuse \(2^{n^2}\) with \((2^n)^2=2^{2n}\).

Common pitfalls

Pitfall What to do instead
\(a^m a^n=a^{mn}\) Sum exponents for product of powers
\((a^m)^n=a^{m+n}\) Multiply exponents
\(\log(x+y)=\log x+\log y\) Product inside log, not sum
Logs of nonpositives Domain \(x>0\)
Base \(1\) or negative Base \(b>0\), \(b\neq 1\)
Forgetting \(\sqrt{x^2}=|x|\) Absolute value
Bits for \(0..2^k-1\) off-by-one Exactly \(k\) bits for \(2^k\) values

Fully worked extra examples

E15 — Log equation domain.
\(\log_2(x-1)+\log_2(x+1)=3\Rightarrow\log_2((x-1)(x+1))=3\Rightarrow x^{2}-1=8\Rightarrow x^{2}=9\Rightarrow x=\pm 3\). Domain \(x>1\), so \(x=3\) only.

E16 — Bits vs values.
\(k\) bits distinguish \(2^{k}\) patterns. For \(N\) values, need \(\lceil\log_2 N\rceil\) bits. Off-by-one: \(0..2^{k}-1\) uses \(k\) bits exactly.

E17 — Change of base chain.
\(\log_2 3\cdot\log_3 5\cdot\log_5 2=1\) by telescoping change-of-base (each \(\frac{\ln a}{\ln b}\) multiplies to \(1\)).

E18 — Exponential inequality preview.
For \(b>1\), \(b^{x}>b^{y}\Leftrightarrow x>y\). Used when comparing growth without solving equality.

End-of-day synthesis problems

S1. Prove \(a^{m}a^{n}=a^{m+n}\) for \(m,n\ge 0\) by induction on \(n\).

S2. Simplify \(\dfrac{(2^{3})^{4}\cdot 2^{-5}}{4^{2}}\) fully to a power of \(2\).

S3. Evaluate \(\log_2 80\) using \(\log_2 5\) left symbolic: \(4+\log_2 5\).

S4. Change of base: compute \(\log_9 27\) exactly.

S5. Bits for \(0..10^{6}-1\); bit length of \(10^{6}\).

S6. Solve \(5^{x+1}=25^{x-1}\).

S7. Solve \(\log_2(x-1)+\log_2(x+1)=3\) with domain check.

S8. Password space \(26^{8}\): express \(\log_2(26^{8})\) as \(8\log_2 26\).

Checkpoint

  • State and prove (sketch) main exponent laws
  • Define \(\log_b x\) and invert with \(b^y\)
  • Apply product/power/change-of-base laws
  • Compute bit counts via \(\lceil\log_2 N\rceil\)
  • Solve \(b^x=c\) and same-base exponential equations
  • Write S1 proof cleanly

Write two takeaways in your own words.

Deep dive — exponent laws, logs, bits

D1 — Induction writeup for \(a^m a^n=a^{m+n}\) (\(n\ge 0\)).
Fix \(m\ge 0\), induct on \(n\). Base \(n=0\): \(a^m\cdot a^0=a^m\cdot 1=a^m=a^{m+0}\).
Assume for \(n\): \(a^m a^n=a^{m+n}\). Then \(a^m a^{n+1}=a^m a^n a=a^{m+n}a=a^{m+n+1}\).
Negatives: reduce using \(a^{-k}=1/a^k\) and Law 4 once nonnegative cases are solid.

D2 — Change of base chain telescopes.
\(\log_2 3\cdot\log_3 5\cdot\log_5 2=\frac{\ln 3}{\ln 2}\cdot\frac{\ln 5}{\ln 3}\cdot\frac{\ln 2}{\ln 5}=1\).
Useful check when converting bases repeatedly.

D3 — Solve with substitution.
\(2^{2x}-2^{x}-2=0\). Let \(u=2^{x}>0\). Then \(u^2-u-2=0\), \((u-2)(u+1)=0\), \(u=2\) (discard \(-1\)). So \(2^{x}=2\), \(x=1\).

D4 — Bits and off-by-one.
Values \(0..2^{k}-1\): exactly \(k\) bits.
Values \(0..N-1\): \(\lceil\log_2 N\rceil\) bits for \(N\ge 2\).
Bit length of integer \(n>0\): \(\lfloor\log_2 n\rfloor+1\) (e.g. \(n=1000\) needs \(10\) bits).

D5 — Same-base exponential equation.
\(9^{x}=27^{x-1}\): \((3^2)^{x}=(3^3)^{x-1}\), \(2x=3x-3\), \(x=3\).
Check: \(9^3=729\), \(27^{2}=729\).

D6 — Log domain checklist.
\(\log_2(x^2-1)\) needs \(x^2-1>0\), i.e. \(x<-1\) or \(x>1\).
After solving \(\log_2(x-1)+\log_2(x+1)=3\), only candidates with both factors positive (or careful product domain) survive—here \(x>1\), so \(x=3\) only from \(\pm 3\).

Extra practice set

  1. Prove \(\log_b(x/y)=\log_b x-\log_b y\) from definitions.
  2. Simplify \(\dfrac{(2^{3})^{4}\cdot 2^{-5}}{4^{2}}\) to a power of \(2\).
  3. How many bits to store unsigned integers up to \(10^{9}\)?
  4. Solve \(5^{2x}-5^{x}-6=0\) with \(u=5^{x}\).
  5. Express \(\log_2(6^{n})\) as \(n(1+\log_2 3)\).

Tomorrow

Day 9 — Error, rounding & floating-point idea. Absolute/relative error, rounding vs truncation, catastrophic cancellation, machine epsilon idea, error propagation lite.