Question:

Exercise 0.3.11 Claim: for all . Step 1 — Base case. For , . Explanation: checked the smallest natural number. Step 2 — Induction. Assume . Then k+1 \le 2k \quad(\text{for }k\ge1), Explanation: used and doubled the induction hypothesis. Final answer: True for all . --- Exercise 0.3.12 Claim: If finite, then . Step 1 — Base case. If then and has size . Explanation: power set of empty set has one subset. Step 2 — Induction / doubling argument. If and we add a new element to make , every subset of either contains or not. Thus subsets of are exactly the subsets of plus those same subsets with adjoined, so . Explanation: each subset comes in an “-absent / -present” pair, doubling the count. Final answer: . --- Exercise 0.3.13 Claim: Step 1 — Telescoping decomposition. Note . Explanation: algebraic partial fraction decomposition. Step 2 — Sum and telescope. \sum_{k=1}^n\left(\frac{1}{k}-\frac{1}{k+1}\right)=1-\frac{1}{n+1}=\frac{n}{n+1}. Final answer: . --- Exercise 0.3.14 Claim: . Step 1 — Base case. For : . Explanation: base check holds. Step 2 — Induction. Assume for . Then \sum_{i=1}^{k+1} i^3 = \Big(\frac{k(k+1)}{2}\Big)^2 +(k+1)^3. \Big(\frac{(k+1)(k+2)}{2}\Big)^2 - \Big(\frac{k(k+1)}{2}\Big)^2 = (k+1)^3, Explanation: algebraic identity shows the square expression increases exactly by . Final answer: . --- Exercise 0.3.15 Claim: is divisible by for all . Step 1 — Rearrange. Write n^3+5n=(n^3-n)+6n. Step 2 — Use factorization. which is product of three consecutive integers, hence divisible by and by , so divisible by . Also is divisible by . Sum of two multiples of is a multiple of . Explanation: consecutive-integer product gives divisibility by . Final answer: for all . --- Exercise 0.3.16 Claim: Find smallest with , call it , and show inequality for all . Step 1 — Search small integers. Compute LHS and RHS: : , so false. : , so true. Hence . Explanation: test small to find first satisfying inequality. Step 2 — Monotonicity to propagate truth. Let . Compute f(n+1)-f(n)=3n^2-n-21=3n^2-n-21. Explanation: once the difference becomes positive at and the function is increasing, it remains positive. Final answer: , and the inequality holds for every . --- Exercise 0.3.17 Claim: Find all with . Step 1 — Check small . 1^2