Exercise · ZW-STRONG-INDUCTION-010 · ★★★ Advanced
To prove every \(n\ge1\) is a sum of distinct powers of \(2\), if \(n+1\) is even, what is used?
Choose one option.
Show answer
- C. \(P\big(\tfrac{n+1}{2}\big)\), doubling each power
Explanation
If \(n+1\) is even, \(\tfrac{n+1}2\le n\) is a sum of distinct powers; multiplying them by \(2\) keeps them distinct. Here \(P(n)\) is not enough, because adding \(1\) might repeat \(2^0\).
Review the concept: Strong induction
Strong induction proves \(P(n)\) for every \(n\ge n_0\): after checking the base case \(P(n_0)\), one proves \(P(k+1)\) assuming \(P(j)\) for all \(j\) with \(n_0\le j\le k\).
\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(n_0)\wedge\cdots\wedge P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]
More practice problems: strong induction
- ZW-STRONG-INDUCTION-001 In the step of a strong induction proving P(k+1), the hypothesis is:
- ZW-STRONG-INDUCTION-002 An inductive step proves P(k+1) using P(k) and P(k-1). At least how many base cases are needed?
- ZW-STRONG-INDUCTION-003 With F_1=F_2=1 and F_n=F_n-1+F_n-2, what is F_10?
- ZW-STRONG-INDUCTION-004 To prove that every integer n≥2 is a product of primes, if k+1=ab with 2≤ a,b≤ k, which hypothesis…
- ZW-STRONG-INDUCTION-005 Compared with ordinary mathematical induction, strong induction:
- ZW-STRONG-INDUCTION-006 Let a_1=1, a_2=2 and a_n=a_n-1+a_n-2. What is a_8?
- ZW-STRONG-INDUCTION-007 With stamps of 4 and 5 cents, what is the least n_0 such that every amount n≥ n_0 can be made?
- ZW-STRONG-INDUCTION-008 Let a_0=0, a_1=1 and a_n=3a_n-1-2a_n-2. It is proved by strong induction that a_n=2^n-1. What is a_…