- Check whether the argument assumes what it is trying to prove. - Distinguish carefully between the current index and the next index.

1. The proof assumes the very statement for \(k+1\) that it is supposed to prove. This is circular reasoning. 2. The correct inductive hypothesis assumes only that the claim is true for an arbitrary \(k\). 3. That assumption must then be used to prove the claim for \(k+1\).

The argument is circular. The inductive hypothesis must assume the statement for \(k\), not for \(k+1\).

- The hypothesis should be the same statement with a fixed index. - Express the next case as the previous case plus an additional term.

1. Hypothesis A is appropriate because it is the original statement at the index \(k\). 2. Assume \(k(k+1)\) is even for an arbitrary \(k\ge0\). 3. Rewrite the next case: \((k+1)(k+2)=k(k+1)+2(k+1)\). 4. The first term is even by the inductive hypothesis, and the second term is a multiple of \(2\). Therefore, \((k+1)(k+2)\) is even.

A is correct. Since \((k+1)(k+2)=k(k+1)+2(k+1)\), the next expression is even.

- Identify the first value for which the statement is supposed to hold. - Substitute that smallest allowed value into both sides.

1. The statement is defined only for \(n>1\), so checking \(n=1\) does not verify a value in the stated domain. 2. The smallest integer satisfying \(n>1\) is \(n=2\). 3. For \(n=2\), the left side is \(2\), and the right side is \(\frac{2\cdot3}{2}-1=2\). Thus, the correct base case is valid.

The base case must be \(n=2\); both sides equal \(2\).

- Check the two required parts of an induction proof separately. - Ask whether the first statement in the proposed chain is true.

1. The transition from \(k\) to \(k+1\) would be algebraically valid if the hypothesis \(k=k+1\) were true. 2. However, there is no valid base case. For example, \(1=2\) is false. 3. Without a true base case, the inductive step cannot establish any chain of true statements.

The base case is missing and cannot be true. A valid inductive step alone proves nothing without a true starting case.

- Use the recursive definition first and the inductive hypothesis second. - Each equality should have a clear justification.

1. Assume the inductive hypothesis \(a_k=2^k+1\) for an arbitrary integer \(k\ge1\). 2. First use the recurrence, and then substitute the inductive hypothesis: \(a_{k+1}=2a_k-1=2(2^k+1)-1=2^{k+1}+1\). 3. This justifies the inductive step. The base case also holds because \(a_1=3=2^1+1\).

The missing calculation is \(a_{k+1}=2a_k-1=2(2^k+1)-1=2^{k+1}+1\).

- Find the smallest integer covered by the claim. - Check the two sides at that integer separately. - Ask what would still need to be shown for every later integer.

1. The smallest allowed value is \(n=1\). The left side is \(1\); the right side is \(\frac{1(1+1)}{2}=1\). 2. The base case is true, but one case does not prove the claim for all positive integers. An inductive step is still required.

At \(n=1\), \(1=\frac{1(2)}{2}=1\). The base case works, but it does not complete the induction proof.

- Keep the same claim but replace the index \(n\) first by \(k\), then by \(k+1\). - Separate what the induction hypothesis permits from what the proof still needs to establish.

1. The induction hypothesis is \(P(k):2^k>k\), for an arbitrary integer \(k\ge1\). 2. The next statement is \(P(k+1):2^{k+1}>k+1\). 3. Assuming \(P(k+1)\) would assume the very claim being proved. The step must use \(P(k)\) to establish it.

a) Assume \(2^k>k\). b) Prove \(2^{k+1}>k+1\); this next claim cannot be assumed in advance.

- Use the bounds to decide which index values belong in the first product. - Compare the two upper bounds. Which index appears in the longer product but not the shorter one?

1. For \(n=4\), the factors come from \(j=2,3,4\), so \(P(4)=3\cdot4\cdot5=60\). 2. Extending the product to \(n=5\) adds the factor obtained at \(j=5\), which is \(6\). Thus \(P(5)=P(4)\cdot6=360\).

a) \(P(4)=3\cdot4\cdot5=60\). b) Multiply by \(6\); \(P(5)=360\).

- Separate what the row for the first allowed value establishes from what the remaining example rows establish. - Ask what must connect an arbitrary case to the next case in an induction proof.

1. The table checks only five values, so by itself it cannot prove a statement about every positive integer. 2. The row for \(n=1\) verifies the required base case. 3. What remains is a general inductive step: assume for an arbitrary \(k\ge1\) that \(1+3+\cdots+(2k-1)=k^2\), and then prove from that assumption that \(1+3+\cdots+(2k+1)=(k+1)^2\).

The table provides only finitely many examples. It already verifies the base case \(n=1\); a proof by induction still needs a general step showing that truth for an arbitrary \(k\ge1\) implies truth for \(k+1\).

- Verify the smallest allowed value first. - Compare the sums for two consecutive values of \(n\).

1. Base case: For \(n=1\), \(2=1\cdot2\), so the statement is true. 2. Inductive hypothesis: Assume that \(2+4+\cdots+2k=k(k+1)\) for an arbitrary \(k\ge1\). 3. Inductive step: Add the next term, \(2(k+1)\): \(2+4+\cdots+2k+2(k+1)=k(k+1)+2(k+1)=(k+1)(k+2)\). 4. Therefore, the formula holds for \(k+1\), and by induction it holds for every \(n\ge1\).

For every integer \(n\ge1\), \(2+4+\cdots+2n=n(n+1)\).

- Test the listed starting values in order. - Compare how the two sides change when the index increases by \(1\).

1. Base case: For \(n=0\), \(2^0=1=0+1\). Therefore, \(n_0=0\) works and is the smallest listed value. 2. Inductive hypothesis: Assume \(2^k\ge k+1\) for an arbitrary \(k\ge0\). 3. Inductive step: \(2^{k+1}=2\cdot2^k\ge2(k+1)=2k+2\ge k+2\) because \(k\ge0\). 4. Therefore, \(2^n\ge n+1\) for every integer \(n\ge0\).

\(n_0=0\); the inequality holds for every integer \(n\ge0\).

- Isolate the single new term added at the next index. - Combine the resulting expressions over a common denominator.

1. Base case: For \(n=1\), the left side is \(2\), and the right side is \(\frac{1\cdot4}{2}=2\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}(3j-1)=\frac{k(3k+1)}{2}\) for an arbitrary \(k\ge1\). 3. Add the next term: \(\sum_{j=1}^{k+1}(3j-1)=\frac{k(3k+1)}{2}+3(k+1)-1\). 4. Simplifying gives \(\frac{k(3k+1)+6k+4}{2}=\frac{(k+1)(3k+4)}{2}\), which is the stated formula with \(k+1\) in place of \(n\). 5. Therefore, the identity holds for every \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}(3j-1)=\frac{n(3n+1)}{2}\).

- Rewrite the expression with exponent \(k+1\) using the expression with exponent \(k\). - Separate it into a term covered by the hypothesis and an obviously divisible term.

1. Base case: For \(n=1\), \(7^1-1=6\), which is divisible by \(6\). 2. Inductive hypothesis: Assume \(7^k-1\) is divisible by \(6\) for an arbitrary \(k\ge1\). 3. Rewrite the next case: \(7^{k+1}-1=7(7^k-1)+6\). 4. The first term is divisible by \(6\) by the inductive hypothesis, and the second term is divisible by \(6\). Therefore, \(7^{k+1}-1\) is divisible by \(6\). 5. The statement follows by induction.

For every integer \(n\ge1\), \(6\mid(7^n-1)\).

- Compare the recursive increase with the change in the proposed formula. - First check that the formula matches the initial value.

1. Base case: For \(n=1\), \(a_1=4=3\cdot1+1\). 2. Inductive hypothesis: Assume \(a_k=3k+1\) for an arbitrary \(k\ge1\). 3. Then \(a_{k+1}=a_k+3=3k+1+3=3(k+1)+1\). 4. Therefore, the formula holds for every \(n\ge1\).

For every integer \(n\ge1\), \(a_n=3n+1\).

- Look for a value that makes the expression visibly factorable. - One counterexample is enough to disprove a universal statement.

1. Checking finitely many values cannot prove a statement about every nonnegative integer. 2. For \(n=41\), \(n^2+n+41=41^2+41+41=41\cdot(41+2)=41\cdot43\). 3. This value is composite, so the universal claim is false.

The claim is false. At \(n=41\), the expression equals \(41\cdot43\), which is not prime.

- Compare two consecutive perfect squares. - Identify the new odd term added at the next index.

1. Base case: For \(n=1\), \(1=1^2\). 2. Inductive hypothesis: Assume \(1+3+\cdots+(2k-1)=k^2\) for an arbitrary \(k\ge1\). 3. Add the next odd number, \(2k+1\): \(1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2\). 4. Therefore, the identity holds for every \(n\ge1\).

For every integer \(n\ge1\), \(1+3+5+\cdots+(2n-1)=n^2\).

- Factor common terms before fully expanding. - The new summand already contains factors from the target expression.

1. Base case: For \(n=1\), \(1\cdot2=\frac{1\cdot2\cdot3}{3}\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}j(j+1)=\frac{k(k+1)(k+2)}{3}\) for an arbitrary \(k\ge1\). 3. Add the next term: \(\sum_{j=1}^{k+1}j(j+1)=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)\). 4. Factor to obtain \(\frac{(k+1)(k+2)(k+3)}{3}\), which is the formula for \(k+1\). 5. Therefore, the identity holds for every \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}j(j+1)=\frac{n(n+1)(n+2)}{3}\).

- Identify the next term by its exponent. - Combine powers with the same base as soon as possible.

1. Base case: For \(n=1\), \(2=3-1\). 2. Inductive hypothesis: Assume \(2+6+\cdots+2\cdot3^{k-1}=3^k-1\) for an arbitrary \(k\ge1\). 3. Add the next term \(2\cdot3^k\): \(3^k-1+2\cdot3^k=3\cdot3^k-1=3^{k+1}-1\). 4. Therefore, the formula holds for every \(n\ge1\).

For every integer \(n\ge1\), \(2+6+\cdots+2\cdot3^{n-1}=3^n-1\).

- What changes in the product when its upper bound increases from \(k\) to \(k+1\)? - How could the assumed product help you calculate the longer product?

1. Base case: For \(n=1\), the product is \(1+\frac{1}{1}=2\), which equals \(1+1\). 2. Inductive hypothesis: Assume \(\prod_{j=1}^{k}\left(1+\frac{1}{j}\right)=k+1\) for an arbitrary integer \(k\ge1\). 3. The next factor is \(1+\frac{1}{k+1}=\frac{k+2}{k+1}\). Therefore, \(\prod_{j=1}^{k+1}\left(1+\frac{1}{j}\right)=(k+1)\cdot\frac{k+2}{k+1}=k+2\). 4. This proves the claim at \(k+1\), so the identity holds for all integers \(n\ge1\).

Base case: \(n=1\) gives \(2\). If the product through \(k\) is \(k+1\), multiply by the next factor \(\frac{k+2}{k+1}\) to obtain \(k+2\). Thus the formula holds by induction.

- When multiplying powers with the same base, add the exponents. - Compare consecutive perfect squares.

1. Base case: At \(n=1\), \(2^1=2^{1^2}\). 2. Assume \(\prod_{j=1}^{k}2^{2j-1}=2^{k^2}\) for an arbitrary integer \(k\ge1\). 3. Multiply by \(2^{2(k+1)-1}=2^{2k+1}\) to get \(2^{k^2}\cdot2^{2k+1}=2^{k^2+2k+1}=2^{(k+1)^2}\). 4. Therefore the formula holds for every integer \(n\ge1\).

The identity holds at \(n=1\). Assuming the product through \(k\) is \(2^{k^2}\), the next factor gives \(2^{k^2}\cdot2^{2k+1}=2^{(k+1)^2}\). The identity follows by induction.

- Rewrite the expression for the next integer so that the previous expression appears. - Use a basic property of two consecutive integers.

1. Base case: For \(n=0\), \(n^3-n=0\), which is divisible by \(6\). 2. Inductive hypothesis: Assume \(k^3-k\) is divisible by \(6\) for an arbitrary integer \(k\ge0\). 3. For the next integer, \((k+1)^3-(k+1)=(k^3-k)+3k(k+1)\). 4. The first term is divisible by \(6\) by the inductive hypothesis. Because one of the consecutive integers \(k\) and \(k+1\) is even, \(k(k+1)\) is even, so \(3k(k+1)\) is also divisible by \(6\). 5. Therefore, \((k+1)^3-(k+1)\) is divisible by \(6\), and the statement holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(6\mid(n^3-n)\).

- The first allowed value of the index strongly restricts \(c\). - Then rewrite the expression for the next index using the previous one.

1. At \(n=0\), \(1+c\) must be divisible by \(4\). Among the given choices, this requires \(c=3\). 2. Base case: For \(n=0\), \(5^0+3=4\), which is divisible by \(4\). 3. Inductive hypothesis: Assume \(5^k+3\) is divisible by \(4\) for an arbitrary integer \(k\ge0\). 4. For the next integer, \(5^{k+1}+3=5(5^k+3)-12\). 5. Both terms on the right are divisible by \(4\), so \(5^{k+1}+3\) is divisible by \(4\). 6. Therefore, \(4\mid(5^n+3)\) for every integer \(n\ge0\).

\(c=3\). For this value, \(4\mid(5^n+3)\) for every integer \(n\ge0\).

- Treat \(a\) as a fixed parameter and use induction only on the exponent. - Rewrite the new expression so that the previous exponent appears.

1. Base case: For \(n=0\), \(a^0-1=0\), which is divisible by \(a-1\). 2. Inductive hypothesis: For a fixed integer \(a\ge2\), assume \(a^k-1\) is divisible by \(a-1\) for an arbitrary integer \(k\ge0\). 3. For the next exponent, \(a^{k+1}-1=a(a^k-1)+(a-1)\). 4. Both terms on the right are divisible by \(a-1\), so \(a^{k+1}-1\) is also divisible by \(a-1\). 5. Therefore, the statement holds for every integer \(n\ge0\).

For every integer \(a\ge2\) and every integer \(n\ge0\), \((a-1)\mid(a^n-1)\).

- After using the inductive hypothesis, compare two linear expressions. - Pay attention to the starting value \(0\).

1. Base case: For \(n=0\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(3^k\ge2k+1\) for an arbitrary integer \(k\ge0\). 3. Then \(3^{k+1}=3\cdot3^k\ge3(2k+1)=6k+3\). 4. Since \(6k+3\ge2k+3=2(k+1)+1\) for \(k\ge0\), it follows that \(3^{k+1}\ge2(k+1)+1\). 5. Therefore, the inequality holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(3^n\ge2n+1\).

- Use the relationship between consecutive factorials. - After applying the inductive hypothesis, estimate the new factor.

1. First check \(n=0\): \(0!=1\ge2^{-1}=\frac12\). Also, for \(n=1\), \(1!=1=2^0\). 2. Inductive hypothesis: Assume \(k!\ge2^{k-1}\) for an arbitrary integer \(k\ge1\). 3. Then \((k+1)!=(k+1)k!\ge(k+1)2^{k-1}\). 4. Since \(k+1\ge2\), \((k+1)!\ge2\cdot2^{k-1}=2^k\), which is the inequality for \(k+1\). 5. Together with the separately verified case \(n=0\), the inequality holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(n!\ge2^{n-1}\).

- Find a simple upper bound for the new term. - Compare that bound with the increase on the right side.

1. Base case: For \(n=1\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(1+\frac12+\cdots+\frac1k\le\frac{k+1}{2}\) for an arbitrary integer \(k\ge1\). 3. After adding the next term, the new sum is at most \(\frac{k+1}{2}+\frac{1}{k+1}\). 4. Since \(k\ge1\), \(\frac{1}{k+1}\le\frac12\). Therefore, \(\frac{k+1}{2}+\frac{1}{k+1}\le\frac{k+1}{2}+\frac12=\frac{k+2}{2}\). 5. This is the inequality for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}\frac1j\le\frac{n+1}{2}\).

- An exact formula may be easier to prove than the inequality alone. - Compare the remainder terms for consecutive indices.

1. We prove the stronger identity \(1+\frac12+\frac1{2^2}+\cdots+\frac1{2^n}=2-\frac1{2^n}\). For \(n=0\), \(1=2-\frac1{2^0}<2\). 2. Inductive hypothesis: Assume \(1+\frac12+\cdots+\frac1{2^k}=2-\frac1{2^k}\) for an arbitrary integer \(k\ge0\). 3. Add the next term: \(2-\frac1{2^k}+\frac1{2^{k+1}}=2-\frac1{2^{k+1}}<2\). 4. Therefore, the identity, and hence the required inequality, holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(1+\frac12+\cdots+\frac1{2^n}=2-\frac1{2^n}<2\).

- Substitute the proposed formula directly into the recurrence. - Track the one-unit shift in the exponent.

1. Base case: For \(n=1\), \(a_1=3=2^2-1\). 2. Inductive hypothesis: Assume \(a_k=2^{k+1}-1\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(a_{k+1}=2a_k+1=2(2^{k+1}-1)+1=2^{k+2}-1\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(a_n=2^{n+1}-1\).

- Check the exponent in the first term. - The recurrence multiplies by the same factor each time.

1. Base case: For \(n=1\), \(a_1=1=3^0\). 2. Inductive hypothesis: Assume \(a_k=3^{k-1}\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(a_{k+1}=3a_k=3\cdot3^{k-1}=3^k\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(a_n=3^{n-1}\).

- Observe the regular sign change. - Compare it with consecutive powers of \(-1\).

1. Base case: For \(n=1\), \(a_1=-2=2(-1)^1\). 2. Inductive hypothesis: Assume \(a_k=2(-1)^k\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(a_{k+1}=-a_k=-2(-1)^k=2(-1)^{k+1}\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(a_n=2(-1)^n\).

- Carry the lower and upper bounds through the recurrence separately. - The recurrence is increasing in \(a_n\).

1. Base case: For \(n=1\), \(1\le a_1<2\). 2. Inductive hypothesis: Assume \(1\le a_k<2\) for an arbitrary integer \(k\ge1\). 3. For the lower bound, \(a_{k+1}=\frac{a_k+2}{2}\ge\frac{1+2}{2}=\frac32\ge1\). 4. For the upper bound, \(a_k<2\) implies \(a_{k+1}<\frac{2+2}{2}=2\). 5. Thus, \(1\le a_{k+1}<2\), and the bounds hold for every integer \(n\ge1\).

For every integer \(n\ge1\), \(1\le a_n<2\).

- Substitute the proposed formula into the recurrence. - Compare the resulting numerator with the target expression for the next index.

1. Base case: For \(n=1\), \(S_1=2=\frac{3+1}{2}\). 2. Inductive hypothesis: Assume \(S_k=\frac{3k^2+k}{2}\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(S_{k+1}=\frac{3k^2+k}{2}+3k+2=\frac{3k^2+7k+4}{2}\). 4. Since \(3k^2+7k+4=3(k+1)^2+(k+1)\), \(S_{k+1}=\frac{3(k+1)^2+(k+1)}{2}\). 5. Therefore, the formula holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(S_n=\frac{3n^2+n}{2}\).

- Sort the new subsets by whether they contain the new element. - Pair them uniquely with subsets of the original set.

1. Base case: The empty set has exactly one subset, and \(1=2^0\). 2. Inductive hypothesis: Assume a set with \(k\) elements has exactly \(2^k\) subsets for an arbitrary integer \(k\ge0\). 3. Add one new element. Each subset of the original set corresponds to exactly two subsets of the new set: one that excludes the new element and one that includes it. 4. Therefore, the number of subsets doubles from \(2^k\) to \(2^{k+1}\). 5. Thus, a set with \(n\) elements has exactly \(2^n\) subsets for every integer \(n\ge0\).

A set with \(n\) elements has exactly \(2^n\) subsets for every integer \(n\ge0\).

- Count only the additional handshakes made by the new person. - The existing handshakes do not change.

1. Base case: With \(n=0\) people, there are \(0=\frac{0\cdot(0-1)}{2}\) handshakes. 2. Inductive hypothesis: Assume \(k\) people make \(\frac{k(k-1)}{2}\) handshakes for an arbitrary integer \(k\ge0\). 3. One new person shakes hands once with each of the \(k\) existing people, adding \(k\) handshakes. 4. The new total is \(\frac{k(k-1)}{2}+k=\frac{k(k+1)}{2}\), which is the formula for \(k+1\). 5. Therefore, the formula holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(n\) people make exactly \(\frac{n(n-1)}{2}\) handshakes.

- Use the diagram to focus on what changes at the end of the row when one new square is attached. - Compare the boundary side that becomes shared with the new sides contributed by the added square. - Express the net boundary change so it can be applied to the inductive hypothesis.

1. Base case: For \(n=1\), the boundary consists of \(4=2\cdot1+2\) sides. 2. Assume the boundary of a row of \(k\ge1\) squares consists of \(2k+2\) square sides. 3. Attaching one more square makes one boundary side interior but contributes three new boundary sides, increasing the total by \(2\). 4. The new boundary has \(2k+2+2=2(k+1)+2\) square sides. 5. By induction the boundary has \(2n+2\) square sides for every integer \(n\ge1\).

One square has \(4=2\cdot1+2\) outside sides. Adding a square removes one outside side and adds three, a net gain of \(2\). Thus \(2k+2\) sides become \(2(k+1)+2\), proving the formula by induction.

- Rewrite both fractions using a common denominator. - Compare the result with the target formula at the next index.

1. Use a common denominator: \(\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}\). 2. Since \(k(k+2)+1=(k+1)^2\), \(\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}\). 3. This is exactly the claimed right side with \(n=k+1\), so the inductive step is complete.

The missing expression is \(\frac{k+1}{k+2}\).

- Check the claimed bound at each of the two defined starting indices. - Write the recurrence for \(u_{k+1}\). Which of its two terms is not controlled by Maya's assumption? - Once both earlier terms are bounded, compare their sum with the target power of \(2\).

1. At \(n=0\), \(u_0=1\le2^0=1\); at \(n=1\), \(u_1=2\le2^1=2\). 2. The next term is \(u_{k+1}=u_k+u_{k-1}\). A bound for \(u_k\) alone gives no bound for \(u_{k-1}\). She also needs \(u_{k-1}\le2^{k-1}\), supplied by assuming the claim for all indices through \(k\) in strong induction. 3. Using both bounds, \(u_{k+1}=u_k+u_{k-1}\le2^k+2^{k-1}=3\cdot2^{k-1}\le4\cdot2^{k-1}=2^{k+1}\). This completes the strong-induction step.

a) \(u_0=1\le1\), and \(u_1=2\le2\). b) The missing bound is \(u_{k-1}\le2^{k-1}\). Both earlier terms appear in the recurrence, so her hypothesis about \(u_k\) alone is not enough. c) \(u_{k+1}\le2^k+2^{k-1}=3\cdot2^{k-1}\le2^{k+1}\).

- Keep the entire expression at \(k\) together when comparing consecutive indices. - Expand the expression at \(k+1\) and simplify the subtraction. - Decide what it means when a known multiple of \(3\) gains another multiple of \(3\).

1. The base case is \(1^3+2(1)=3\), a multiple of \(3\). 2. Assume \(k^3+2k\) is divisible by \(3\), where \(k\ge1\). 3. The difference is \(((k+1)^3+2(k+1))-(k^3+2k)=3k^2+3k+3=3(k^2+k+1)\). 4. The next expression is the sum of two multiples of \(3\): the expression at \(k\) and the difference. Therefore it is divisible by \(3\). 5. The claim holds for every integer \(n\ge1\) by induction.

The difference is \(3(k^2+k+1)\), a multiple of \(3\). Adding it to the assumed multiple of \(3\) proves the next case.

- This recurrence refers to two earlier terms, so check the first two cases. - In the inductive step, apply the assumed bound separately to each earlier term. - Compare the resulting powers of \(3\) with the power you need.

1. At \(n=0\), \(v_0=1\le3^0=1\). At \(n=1\), \(v_1=2\le3^1=3\). 2. Assume \(v_j\le3^j\) for all integers \(j\) from \(0\) through some \(k\ge1\). 3. Then \(v_{k+1}=2v_k+v_{k-1}\le2\cdot3^k+3^{k-1}=7\cdot3^{k-1}\le9\cdot3^{k-1}=3^{k+1}\). 4. Thus the bound holds at \(k+1\), and the claim follows for all \(n\ge0\).

The base cases hold: \(v_0=1\le1\) and \(v_1=2\le3\). Assuming the bounds through \(k\), we have \(v_{k+1}=2v_k+v_{k-1}\le2\cdot3^k+3^{k-1}=7\cdot3^{k-1}\le3^{k+1}\). This completes the strong-induction proof.

- Think about which smaller total you could extend by adding one available stamp. - Check that this smaller total is covered by the strong induction hypothesis. - Work out how many starting totals are needed when the step moves back more than one place.

1. The starting totals work: \(6=3+3\), \(7=3+4\), and \(8=4+4\). 2. Suppose every total from \(6\) through \(k\), with \(k\ge8\), can be made. 3. The number \(k-2\) lies between \(6\) and \(k\), so the hypothesis supplies stamps totaling \(k-2\). Adding one \(3\)-cent stamp makes \(k+1\). 4. The new total follows from a total three cents smaller. The three starting cases ensure the argument works for each later total, completing strong induction.

Check \(6=3+3\), \(7=3+4\), and \(8=4+4\). For \(k\ge8\), make \(k-2\) by the strong induction hypothesis and add a \(3\)-cent stamp to make \(k+1\). These three starting cases are needed because the step uses a total three cents earlier.

- Compare one factorial with the next by isolating its final factor. - Use the assumed bound for the smaller factorial. - Decide how large the added factor must be to obtain the next power of \(2\).

1. Base case: \(1!=1=2^0\). 2. Assume \(k!\ge2^{k-1}\) for some integer \(k\ge1\). 3. Then \((k+1)!=(k+1)k!\ge(k+1)2^{k-1}\). 4. Since \(k+1\ge2\), we have \((k+1)2^{k-1}\ge2^k\), which is the claim at \(k+1\). 5. Therefore \(n!\ge2^{n-1}\) for all integers \(n\ge1\).

The base case holds at \(n=1\). The inductive step follows from \((k+1)!\ge(k+1)2^{k-1}\ge2^k\) for \(k\ge1\).

- Factor out a common term during the inductive step. - Compare the remaining factors with the target form.

1. Base case: For \(n=1\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(1^2+2^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}\) for an arbitrary \(k\ge1\). 3. Add \((k+1)^2\): \(\frac{k(k+1)(2k+1)}{6}+(k+1)^2\). 4. Factor and simplify: \(\frac{k+1}{6}[k(2k+1)+6(k+1)]=\frac{k+1}{6}(2k^2+7k+6)=\frac{(k+1)(k+2)(2k+3)}{6}\). 5. This is the formula for \(k+1\), so the identity holds for every \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}j^2=\frac{n(n+1)(2n+1)}{6}\).

- Track the alternating sign of the next term carefully. - Relate consecutive powers of \(-1\).

1. Base case: For \(n=1\), both sides equal \(1\). 2. Inductive hypothesis: Assume the formula holds for an arbitrary \(k\ge1\). 3. Add the next term \((-1)^{k+2}(k+1)\). Using \((-1)^{k+1}=-(-1)^{k+2}\), the new sum is \(\frac{1-(-1)^{k+2}(2k+1)+4(-1)^{k+2}(k+1)}{4}\). 4. Simplifying gives \(\frac{1+(-1)^{k+2}(2k+3)}{4}\), which is the formula for \(k+1\). 5. Therefore, the identity holds for every \(n\ge1\).

The stated formula holds for every integer \(n\ge1\).

- The new term shares a power of \(2\) with the inductive hypothesis. - Compare the coefficient of the power with the target index.

1. Base case: For \(n=1\), the left side is \(1\), and the right side is \(0\cdot2+1=1\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}j\cdot2^{j-1}=(k-1)2^k+1\) for an arbitrary \(k\ge1\). 3. Add the next term \((k+1)2^k\): \((k-1)2^k+1+(k+1)2^k=2k\cdot2^k+1=k2^{k+1}+1\). 4. This is the formula for \(k+1\), so the identity holds for every \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}j\cdot2^{j-1}=(n-1)2^n+1\).

- Write out what changes when the upper bound increases by one. - Can you rewrite the new factor in a form that is easier to combine with the assumed product? - Compare the combined expression with the claim at the new upper bound.

1. Base case: For \(n=2\), the left side is \(1-\frac{1}{4}=\frac{3}{4}\), equal to \(\frac{2+1}{2\cdot2}\). 2. Assume \(\prod_{j=2}^{k}\left(1-\frac{1}{j^2}\right)=\frac{k+1}{2k}\) for an arbitrary integer \(k\ge2\). 3. The next factor is \(1-\frac{1}{(k+1)^2}=\frac{k(k+2)}{(k+1)^2}\). 4. Thus \(\prod_{j=2}^{k+1}\left(1-\frac{1}{j^2}\right)=\frac{k+1}{2k}\cdot\frac{k(k+2)}{(k+1)^2}=\frac{k+2}{2(k+1)}\). 5. This is the formula at \(k+1\), so the identity holds for all integers \(n\ge2\).

The base case \(n=2\) gives \(\frac{3}{4}\). Assuming the product through \(k\) equals \(\frac{k+1}{2k}\), multiply by \(1-\frac{1}{(k+1)^2}\) and simplify to \(\frac{k+2}{2(k+1)}\), the required formula at \(k+1\).

- Factor out the largest common power in the inductive step. - Look for a perfect-square trinomial.

1. Base case: For \(n=1\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(1^3+2^3+\cdots+k^3=\left(\frac{k(k+1)}{2}\right)^2\) for an arbitrary integer \(k\ge1\). 3. Add the next term: \(\left(\frac{k(k+1)}{2}\right)^2+(k+1)^3=\frac{k^2(k+1)^2}{4}+(k+1)^3\). 4. Factor and simplify: \(\frac{(k+1)^2}{4}(k^2+4k+4)=\frac{(k+1)^2(k+2)^2}{4}=\left(\frac{(k+1)(k+2)}{2}\right)^2\). 5. This is the formula for \(k+1\), so the identity holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}j^3=\left(\frac{n(n+1)}{2}\right)^2\).

- Express the new term as the difference of two fractions. - Track which endpoint term cancels and which new endpoint term appears.

1. Base case: For \(n=1\), the left side is \(\frac14\). The right side is \(\frac13\left(1+\frac12+\frac13-\frac12-\frac13-\frac14\right)=\frac13\left(1-\frac14\right)=\frac14\). 2. Inductive hypothesis: Assume the formula holds for an arbitrary integer \(k\ge1\). 3. To form the sum through \(k+1\), add \(\frac{1}{(k+1)(k+4)}=\frac13\left(\frac{1}{k+1}-\frac{1}{k+4}\right)\). 4. The terms involving \(\frac{1}{k+1}\) cancel, leaving \(\frac13\left(1+\frac12+\frac13-\frac{1}{k+2}-\frac{1}{k+3}-\frac{1}{k+4}\right)\). 5. This is the formula for \(k+1\), so the identity holds for every integer \(n\ge1\).

The stated identity holds for every integer \(n\ge1\).

- Rewrite the two fractions using the same power of \(2\) in the denominator. - Compare the new numerator with the next index.

1. Base case: For \(n=1\), the left side is \(\frac12\), and the right side is \(2-\frac32=\frac12\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}\frac{j}{2^j}=2-\frac{k+2}{2^k}\) for an arbitrary integer \(k\ge1\). 3. Add the next term: \(2-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}}\). 4. Using the common denominator \(2^{k+1}\), this becomes \(2-\frac{2(k+2)-(k+1)}{2^{k+1}}=2-\frac{k+3}{2^{k+1}}\). 5. This is the formula for \(k+1\), so the identity holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}\frac{j}{2^j}=2-\frac{n+2}{2^n}\).

- Look for a common factorial factor in the inductive step. - Use the relationship between consecutive factorials.

1. Base case: For \(n=1\), \(1\cdot1!=1=2!-1\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}j\cdot j!=(k+1)!-1\) for an arbitrary integer \(k\ge1\). 3. Add the next term: \((k+1)!-1+(k+1)(k+1)!\). 4. Factor and simplify: \([1+(k+1)](k+1)!-1=(k+2)(k+1)!-1=(k+2)!-1\). 5. This is the formula for \(k+1\), so the identity holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}j\cdot j!=(n+1)!-1\).

- Account for both the new power of \(11\) and the sign change in \((-1)^n\). - Rewrite the new expression using the previous one and a remainder.

1. Base case: For \(n=0\), \(11^0-(-1)^0=0\), which is divisible by \(12\). 2. Inductive hypothesis: Assume \(11^k-(-1)^k\) is divisible by \(12\) for an arbitrary integer \(k\ge0\). 3. For the next integer, \(11^{k+1}-(-1)^{k+1}=11[11^k-(-1)^k]+12(-1)^k\). 4. Both terms on the right are divisible by \(12\), so the expression for \(k+1\) is divisible by \(12\). 5. Therefore, the statement holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(12\mid\left(11^n-(-1)^n\right)\).

- Compare the expressions for two consecutive integers. - Check whether all coefficients in the difference share a common factor.

1. Base case: For \(n=0\), \(n^5-n=0\), which is divisible by \(5\). 2. Inductive hypothesis: Assume \(k^5-k\) is divisible by \(5\) for an arbitrary integer \(k\ge0\). 3. The difference between the expression for \(k+1\) and the expression for \(k\) is \((k+1)^5-(k+1)-(k^5-k)=5k^4+10k^3+10k^2+5k\) \(=5(k^4+2k^3+2k^2+k)\). 4. This difference is divisible by \(5\). Since \(k^5-k\) is divisible by \(5\), \((k+1)^5-(k+1)\) is also divisible by \(5\). 5. Therefore, the statement holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(5\mid(n^5-n)\).

- Write a general odd exponent in terms of a new integer index. - Determine the factor by which the power changes when that new index increases by \(1\).

1. Every odd exponent can be written as \(2m+1\). The corrected claim is that \(2^{2m+1}+1\) is divisible by \(3\) for every integer \(m\ge0\). 2. Base case: For \(m=0\), \(2^1+1=3\), which is divisible by \(3\). 3. Inductive hypothesis: Assume \(2^{2k+1}+1\) is divisible by \(3\) for an arbitrary integer \(k\ge0\). 4. For the next integer, \(2^{2(k+1)+1}+1=4\cdot2^{2k+1}+1=4(2^{2k+1}+1)-3\). 5. Both terms on the right are divisible by \(3\), so the corrected claim holds for \(k+1\). 6. Therefore, \(3\mid(2^{2m+1}+1)\) for every integer \(m\ge0\).

For every integer \(m\ge0\), \(3\mid(2^{2m+1}+1)\).

- Check the first few values systematically. - The starting value must make both the claim and the inequality used in the inductive step valid.

1. Checking small values gives \(2^1=2>1=1^2\) and \(2^2=4=2^2\), but \(2^3=8<9=3^2\). Thus, \(n=3\) is the smallest counterexample. The smallest new starting value is \(n_0=4\). 2. Base case: For \(n=4\), \(2^4=16=4^2\). 3. Inductive hypothesis: Assume \(2^k\ge k^2\) for an arbitrary integer \(k\ge4\). 4. Then \(2^{k+1}=2\cdot2^k\ge2k^2\). For \(k\ge4\), \(2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2\ge7>0\). Therefore, \(2k^2\ge(k+1)^2\), so \(2^{k+1}\ge(k+1)^2\). 5. Hence, \(2^n\ge n^2\) for every integer \(n\ge4\).

The smallest counterexample is \(n=3\). The smallest suitable new starting value is \(n_0=4\), and \(2^n\ge n^2\) for every integer \(n\ge4\).

- Compare the new term with the increase in the right side. - Simplify the resulting polynomial inequality.

1. Base case: For \(n=2\), \(1^2+2^2=5<8=2^3\). 2. Inductive hypothesis: Assume \(1^2+2^2+\cdots+k^2<k^3\) for an arbitrary integer \(k\ge2\). 3. After adding the next term, \(1^2+2^2+\cdots+k^2+(k+1)^2<k^3+(k+1)^2\). 4. For \(k\ge1\), \((k+1)^3-k^3=3k^2+3k+1>(k+1)^2\). Therefore, \(k^3+(k+1)^2<(k+1)^3\). 5. The inequality holds for every integer \(n\ge2\).

For every integer \(n\ge2\), \(\sum_{j=1}^{n}j^2<n^3\).

- Compare the new term with the previous right side. - Prove a simple auxiliary exponential bound at the same time.

1. We prove the claim together with the auxiliary inequality \(n+1\le2^n\). 2. Base case: For \(n=1\), \(1<2=2^1\), and \(2\le2^1\). 3. Inductive hypothesis: Assume \(1+2+\cdots+k<2^k\) and \(k+1\le2^k\) for an arbitrary integer \(k\ge1\). 4. Then \(1+2+\cdots+(k+1)<2^k+(k+1)\le2^k+2^k=2^{k+1}\). 5. Also, \(k+2\le2(k+1)\le2\cdot2^k=2^{k+1}\), so the auxiliary inequality holds for \(k+1\). 6. Therefore, \(1+2+\cdots+n<2^n\) for every integer \(n\ge1\).

For every integer \(n\ge1\), \(1+2+\cdots+n<2^n\).

- Substitute the proposed fractional form into the recurrence. - Simplify the reciprocal carefully.

1. Base case: For \(n=1\), \(a_1=2=\frac21\). 2. Inductive hypothesis: Assume \(a_k=\frac{k+1}{k}\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(a_{k+1}=2-\frac{1}{a_k}=2-\frac{k}{k+1}=\frac{k+2}{k+1}\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(a_n=\frac{n+1}{n}\).

- Substitute the proposed formula into both the numerator and denominator. - Simplify the complex fraction one step at a time.

1. Base case: For \(n=1\), \(a_1=\frac12=\frac{1}{1+1}\). 2. Inductive hypothesis: Assume \(a_k=\frac{1}{k+1}\) for an arbitrary integer \(k\ge1\). 3. Using the recurrence, \(a_{k+1}=\frac{\frac{1}{k+1}}{1+\frac{1}{k+1}}=\frac{1}{k+2}\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(a_n=\frac{1}{n+1}\).

- Combine the new summand with the previous endpoint term by using the recurrence. - Track the index shift on the right side.

1. Base case: For \(n=1\), \(F_1=1=F_3-1\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}F_j=F_{k+2}-1\) for an arbitrary integer \(k\ge1\). 3. Add the next Fibonacci number: \(\sum_{j=1}^{k+1}F_j=F_{k+2}-1+F_{k+1}=F_{k+3}-1\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}F_j=F_{n+2}-1\).

- Factor out the common Fibonacci number. - Then use the recursive definition exactly once.

1. Base case: For \(n=1\), \(F_1^2=1=F_1F_2\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}F_j^2=F_kF_{k+1}\) for an arbitrary integer \(k\ge1\). 3. Add the next term and factor: \(\sum_{j=1}^{k+1}F_j^2=F_kF_{k+1}+F_{k+1}^2=F_{k+1}(F_k+F_{k+1})\). 4. By the Fibonacci recurrence, \(F_k+F_{k+1}=F_{k+2}\). Thus, the new sum is \(F_{k+1}F_{k+2}\), the formula for \(k+1\). 5. Therefore, the identity holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}F_j^2=F_nF_{n+1}\).

- Check the two interval endpoints separately. - Use that the square-root function is increasing on nonnegative inputs.

1. Base case: For \(n=1\), \(1\le a_1<2\). 2. Inductive hypothesis: Assume \(1\le a_k<2\) for an arbitrary integer \(k\ge1\). 3. For the lower bound, \(a_{k+1}=\sqrt{2+a_k}\ge\sqrt3>1\). 4. For the upper bound, \(a_k<2\) implies \(2+a_k<4\). Since the square-root function is increasing on nonnegative inputs, \(a_{k+1}=\sqrt{2+a_k}<2\). 5. Thus, \(1\le a_{k+1}<2\), and the bounds hold for every integer \(n\ge1\).

For every integer \(n\ge1\), \(1\le a_n<2\).

- In the inductive step, start with an arbitrary convex polygon having \(k+1\) vertices. - Look for a diagonal that separates one triangle from a smaller convex polygon. - Compare the two angle sums after making that split.

1. Base case: Every convex polygon with \(3\) vertices is a triangle, and its interior-angle sum is \(180^\circ=(3-2)\cdot180^\circ\). 2. Inductive hypothesis: Assume every convex polygon with \(k\ge3\) vertices has interior-angle sum \((k-2)\cdot180^\circ\). 3. Consider an arbitrary convex polygon with \(k+1\) vertices. Choose a vertex and draw the diagonal joining its two neighboring vertices. Convexity keeps that diagonal inside the polygon and divides the polygon into a triangle and a convex \(k\)-gon. 4. By the inductive hypothesis, the \(k\)-gon has interior-angle sum \((k-2)\cdot180^\circ\), and the triangle contributes \(180^\circ\). 5. Therefore the original \((k+1)\)-gon has interior-angle sum \((k-2)\cdot180^\circ+180^\circ=(k-1)\cdot180^\circ\), which is the required formula for \(k+1\). 6. Thus the formula holds for every integer \(n\ge3\).

For every convex polygon with \(n\ge3\) vertices, the interior-angle sum is \((n-2)\cdot180^\circ\).

- Focus on the unavoidable move of the largest disk. - Divide the process into the moves before it, that move, and the moves after it. - Each smaller tower is the same type of problem.

1. Base case: One disk needs exactly \(1=2^1-1\) move. 2. Assume moving \(k\ge1\) disks requires at least \(2^k-1\) moves and can be completed in exactly that many moves. 3. For \(k+1\) disks, the top \(k\) disks must be moved to the auxiliary peg before the largest moves, then moved back onto it afterward. This requires at least \((2^k-1)+1+(2^k-1)=2^{k+1}-1\) moves. 4. Each of the two smaller moves can be performed in exactly \(2^k-1\) steps by the hypothesis, so the minimum is achievable. 5. The minimum is \(2^n-1\) for every integer \(n\ge1\).

One disk needs one move. For \(k+1\) disks, moving the largest disk requires moving the \(k\) smaller disks away and then back, giving at least \(2(2^k-1)+1=2^{k+1}-1\) moves. The same procedure achieves that number, so the formula follows by induction.

- Use the known two-event result as the base case. - In the inductive step, treat the union of the first events as one event. - Pairwise exclusivity must be used to show the new event is disjoint from that union.

1. Base case: for \(n=2\), the statement is the given addition rule. 2. Inductive hypothesis: assume the formula holds for \(n=k\) pairwise mutually exclusive events. 3. Let \(U=A_1\cup\cdots\cup A_k\). Pairwise mutual exclusivity implies \(U\cap A_{k+1}=\varnothing\). 4. Apply the two-event rule: \(P(U\cup A_{k+1})=P(U)+P(A_{k+1})\). 5. Substitute the inductive hypothesis for \(P(U)\), obtaining the formula for \(k+1\). Therefore it holds for every \(n\ge2\).

The result follows by induction: combine the first \(k\) events into one union, show that union is disjoint from \(A_{k+1}\), and apply the two-event addition rule.

- Focus on what changes when exactly one line is added. - Consider changing every color on one entire side of the new line. - Check old adjacencies and new adjacencies separately.

1. Base case: With \(0\) lines, there is one region, which can be colored with either color. 2. Inductive hypothesis: Assume a valid two-coloring exists for any arrangement of \(k\) distinct lines. 3. Add one more distinct line. Keep all colors on one side of the new line and switch both colors on the other side. 4. Any pair of regions that were adjacent before the new line was added still have different colors: either neither color changed or both colors changed. 5. Any two regions newly adjacent across the added line came from the same old region. Exactly one of their colors was switched, so their colors are different. 6. Therefore, a valid two-coloring exists for \(k+1\) lines, and the result follows by induction.

The regions formed by any finite number of distinct lines can be two-colored. In the inductive step, switch the colors on one side of the newly added line.

- Rewrite each interior entry in the next row as the sum of two entries from the preceding row. - Handle the endpoint terms carefully when setting the summation limits.

1. Base case: For \(n=0\), \(\binom{0}{0}=1=2^0\). 2. Inductive hypothesis: Assume \(\sum_{j=0}^{k}\binom{k}{j}=2^k\) for an arbitrary integer \(k\ge0\). 3. By Pascal's identity, \(\binom{k+1}{j}=\binom{k}{j}+\binom{k}{j-1}\). Separating the endpoint terms gives \(\sum_{j=0}^{k+1}\binom{k+1}{j}=1+\sum_{j=1}^{k}\left[\binom{k}{j}+\binom{k}{j-1}\right]+1\). 4. Regrouping the two sums yields \(\sum_{j=0}^{k}\binom{k}{j}+\sum_{j=0}^{k}\binom{k}{j}=2^k+2^k=2^{k+1}\). 5. Therefore, the identity holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(\sum_{j=0}^{n}\binom{n}{j}=2^n\).

- Use Pascal's identity to split each binomial coefficient into two terms. - Shift the index in one of the resulting sums carefully. - Then look for a common factor.

1. Base case: For \(n=0\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(\sum_{j=0}^{k}\binom{k}{j}3^j=4^k\) for an arbitrary integer \(k\ge0\). 3. Using Pascal's identity and separating the endpoint terms, \(\sum_{j=0}^{k+1}\binom{k+1}{j}3^j=\sum_{j=0}^{k}\binom{k}{j}3^j+\sum_{j=1}^{k+1}\binom{k}{j-1}3^j\). 4. In the second sum, let \(r=j-1\). Then it becomes \(3\sum_{r=0}^{k}\binom{k}{r}3^r\). By the inductive hypothesis, \(4^k+3\cdot4^k=4\cdot4^k=4^{k+1}\). 5. Therefore, the identity holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(\sum_{j=0}^{n}\binom{n}{j}3^j=4^n\).

- First compare the change in the proposed quadratic formula with the given change. - Then use the recurrence in the inductive step.

1. From \(S_1=7\), \(a+b=7\). Also, \(S_{n+1}-S_n=a[(n+1)^2-n^2]+b[(n+1)-n]=a(2n+1)+b\). 2. Comparing \(a(2n+1)+b\) with \(8n+7\) gives \(2a=8\) and \(a+b=7\). Thus, \(a=4\) and \(b=3\), so the proposed formula is \(S_n=4n^2+3n\). 3. Base case: For \(n=1\), \(4\cdot1^2+3\cdot1=7=S_1\). 4. Inductive hypothesis: Assume \(S_k=4k^2+3k\) for an arbitrary integer \(k\ge1\). 5. Using the recurrence, \(S_{k+1}=S_k+8k+7=4k^2+3k+8k+7=4(k+1)^2+3(k+1)\). 6. Therefore, \(S_n=4n^2+3n\) for every integer \(n\ge1\).

\(S_n=4n^2+3n\), so \(a=4\) and \(b=3\).

- Compare the new term with the increase on the right side. - Rationalize the difference of two square roots.

1. Base case: For \(n=1\), both sides equal \(1\). 2. Inductive hypothesis: Assume \(\sum_{j=1}^{k}\frac{1}{\sqrt{j}}\ge\sqrt{k}\) for an arbitrary integer \(k\ge1\). 3. After adding the next term, the new sum is at least \(\sqrt{k}+\frac{1}{\sqrt{k+1}}\). 4. It is enough to show that \(\frac{1}{\sqrt{k+1}}\ge\sqrt{k+1}-\sqrt{k}\). Rationalizing gives \(\sqrt{k+1}-\sqrt{k}=\frac{1}{\sqrt{k+1}+\sqrt{k}}\le\frac{1}{\sqrt{k+1}}\). 5. Therefore, the new sum is at least \(\sqrt{k+1}\), and the inequality holds for every integer \(n\ge1\).

For every integer \(n\ge1\), \(\sum_{j=1}^{n}\frac{1}{\sqrt{j}}\ge\sqrt{n}\).

- Before multiplying an inequality, determine the sign of the factor. - Compare the result of multiplying by \(1+x\) with the inequality needed for the next index.

1. Fix a real number \(x\ge-1\). Base case: For \(n=1\), both sides equal \(1+x\). 2. Assume \((1+x)^k\ge1+kx\) for an arbitrary integer \(k\ge1\). 3. Since \(1+x\ge0\), multiplication preserves the inequality: \((1+x)^{k+1}\ge(1+kx)(1+x)=1+(k+1)x+kx^2\). 4. As \(kx^2\ge0\), we get \((1+x)^{k+1}\ge1+(k+1)x\). 5. Therefore Bernoulli's inequality holds for every integer \(n\ge1\) and real number \(x\ge-1\).

At \(n=1\), equality holds. Assuming the inequality at \(k\), multiply by \(1+x\ge0\) to get \((1+x)^{k+1}\ge1+(k+1)x+kx^2\ge1+(k+1)x\). This proves the inequality by induction.

- Use both the inductive hypothesis and the restriction on \(x\). - After expanding, bound the quadratic term.

1. Fix a real number \(x\) with \(0\le x\le1\). Base case: For \(n=0\), both sides equal \(1\). 2. Inductive hypothesis: Assume \((1+x)^k\le1+(2^k-1)x\) for an arbitrary integer \(k\ge0\). 3. Since \(1+x\ge0\), multiplying preserves the inequality: \((1+x)^{k+1}\le[1+(2^k-1)x](1+x)=1+2^kx+(2^k-1)x^2\). 4. Because \(0\le x\le1\), \(x^2\le x\). Thus, \((1+x)^{k+1}\le1+2^kx+(2^k-1)x=1+(2^{k+1}-1)x\). 5. Therefore, the inequality holds for every integer \(n\ge0\) and every real number \(x\) in the stated interval.

For every integer \(n\ge0\) and every real number \(x\) with \(0\le x\le1\), \((1+x)^n\le1+(2^n-1)x\).

- Sort the possible sequences by their final move. - The inductive step needs two preceding cases. - Therefore, verify two base cases.

1. Base cases: For \(n=1\), there is one sequence, so \(W_1=1=F_2\). For \(n=2\), there are two sequences, so \(W_2=2=F_3\). 2. Strong inductive hypothesis: For an arbitrary integer \(k\ge2\), assume \(W_m=F_{m+1}\) for every integer \(m\) with \(1\le m\le k\). 3. Every move sequence that reaches step \(k+1\) ends either with a \(1\)-step move after a sequence reaching step \(k\), or with a \(2\)-step move after a sequence reaching step \(k-1\). Therefore, \(W_{k+1}=W_k+W_{k-1}\). 4. Applying the inductive hypothesis, \(W_{k+1}=F_{k+1}+F_k=F_{k+2}\). 5. Thus, \(W_n=F_{n+1}\) for every integer \(n\ge1\).

For every integer \(n\ge1\), \(W_n=F_{n+1}\).

- In the inductive step, begin with an arbitrary polygon having one more vertex than the inductive hypothesis covers. - Compare it with the smaller convex polygon obtained by removing one vertex. - Account separately for diagonals incident to the removed vertex and for the segment joining its two former neighbors.

1. Base case: Every convex polygon with \(3\) vertices is a triangle, and a triangle has \(0=\frac{3(3-3)}{2}\) diagonals. 2. Inductive hypothesis: Assume every convex polygon with \(k\ge3\) vertices has \(\frac{k(k-3)}{2}\) diagonals. 3. Consider an arbitrary convex polygon with \(k+1\) vertices. Remove one vertex and join its two neighboring vertices. The remaining vertices form a convex \(k\)-gon, so by the inductive hypothesis it has \(\frac{k(k-3)}{2}\) diagonals. 4. In the original \((k+1)\)-gon, the removed vertex contributes \(k-2\) diagonals. The segment joining its two neighbors is also a diagonal of the original polygon but is a side of the smaller \(k\)-gon. Therefore the original polygon has \(k-1\) more diagonals than the smaller polygon. 5. Hence the number of diagonals is \(\frac{k(k-3)}{2}+k-1=\frac{(k+1)(k-2)}{2}\), which is the required formula for \(k+1\). 6. Therefore every convex polygon with \(n\ge3\) vertices has exactly \(\frac{n(n-3)}{2}\) diagonals.

Every convex polygon with \(n\ge3\) vertices has exactly \(\frac{n(n-3)}{2}\) diagonals.

- Count only the new regions created when one line is added. - Determine how many segments the existing lines create on the new line.

1. Base case: With \(n=0\) lines, the plane consists of \(1\) region. 2. Inductive hypothesis: Assume \(k\) lines divide the plane into \(1+\frac{k(k+1)}{2}\) regions for an arbitrary integer \(k\ge0\). 3. A new line intersects the existing \(k\) lines at \(k\) distinct points. These points divide the new line into \(k+1\) segments, and each segment splits one existing region into two. 4. Therefore, the number of regions increases by \(k+1\): \(1+\frac{k(k+1)}{2}+k+1=1+\frac{(k+1)(k+2)}{2}\). 5. This is the formula for \(k+1\), so it holds for every integer \(n\ge0\).

For every integer \(n\ge0\), the number of regions is \(1+\frac{n(n+1)}{2}\).

- Compare the expressions for consecutive indices. - Look for a way to use a multiple of the expression assumed divisible by \(9\).

1. Base case: For \(n=0\), \(4^0+24\cdot0-1=0\), which is divisible by \(9\). 2. Assume \(4^k+24k-1\) is divisible by \(9\) for an arbitrary integer \(k\ge0\). 3. Rearranging the next expression gives \(4^{k+1}+24(k+1)-1=4(4^k+24k-1)+9(3-8k)\). 4. The first term is a multiple of \(9\) by the hypothesis, and the second is visibly a multiple of \(9\). Therefore the expression at \(k+1\) is divisible by \(9\). 5. By induction the result holds for every integer \(n\ge0\).

At \(n=0\), the expression is \(0\). If it is divisible by \(9\) at \(k\), then at \(k+1\) it equals \(4(4^k+24k-1)+9(3-8k)\), also divisible by \(9\). The result follows by induction.

- Strong induction allows the next case to use any earlier case already covered, not only the immediately preceding one. - Try enough consecutive starting cases so that a later integer can be connected to one of them by adding an allowed amount. - In the inductive step, relate \(k+1\) to an earlier integer that is guaranteed to lie inside the range of the strong inductive hypothesis.

1. Base cases: \(12=4(3)+5(0)\), \(13=4(2)+5(1)\), \(14=4(1)+5(2)\), and \(15=4(0)+5(3)\). 2. Inductive hypothesis: Let \(k\ge15\) and assume every integer from \(12\) through \(k\) can be written as \(4a+5b\) with nonnegative integers \(a,b\). 3. Consider \(k+1\). Since \(k\ge15\), the integer \(k-3\) is at least \(12\) and at most \(k\). By the strong inductive hypothesis, \(k-3=4a+5b\) for some nonnegative integers \(a,b\). 4. Therefore, \(k+1=(k-3)+4=4(a+1)+5b\), which has the required form. 5. By strong induction, every integer \(n\ge12\) has such a representation.

Every integer \(n\ge12\) can be written as \(n=4a+5b\) for nonnegative integers \(a,b\); the proof requires the consecutive base cases \(12,13,14,15\) and the strong inductive hypothesis covering all integers through \(k\).