Free Math Worksheets

- Consider what finitely many examples can establish about infinitely many cases. - Separate verification of the first case from the transition to the next case.

1. The five calculations verify the claim for only five values. A finite collection of examples does not prove a statement for every positive integer. 2. The base case must verify the claim for the first allowed value. 3. For the inductive step, assume for an arbitrary \(k\ge1\) that \(1+3+\cdots+(2k-1)=k^2\), and use that assumption to prove \(1+3+\cdots+(2k+1)=(k+1)^2\).

The table provides only examples. A proof also needs a valid base case and a general inductive step from \(k\) to \(k+1\).

- 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\).

- 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)\).

- Pay attention to the base case at \(0\). - Isolate the new term added when the upper limit increases by \(1\).

1. Base case: For \(n=0\), the left side is \(1\), and the right side is \((0+1)(2\cdot0+1)=1\). 2. Inductive hypothesis: Assume \(\sum_{j=0}^{k}(4j+1)=(k+1)(2k+1)\) for an arbitrary \(k\ge0\). 3. The next sum adds \(4(k+1)+1=4k+5\). 4. Therefore, \(\sum_{j=0}^{k+1}(4j+1)=(k+1)(2k+1)+4k+5=(k+2)(2k+3)\), which is the required formula for \(k+1\). 5. The identity holds for every \(n\ge0\).

For every integer \(n\ge0\), \(\sum_{j=0}^{n}(4j+1)=(n+1)(2n+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\).

- Rewrite the new factor as a fraction. - Look for factors that cancel in the inductive step.

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 is the formula for \(k+1\), so the identity holds for every integer \(n\ge1\).

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

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

1. Base case: For \(n=1\), \(2^1=2^{1^2}\). 2. Inductive hypothesis: Assume \(\prod_{j=1}^{k}2^{2j-1}=2^{k^2}\) for an arbitrary integer \(k\ge1\). 3. Multiply by the next factor \(2^{2(k+1)-1}=2^{2k+1}\): \(2^{k^2}\cdot2^{2k+1}=2^{k^2+2k+1}=2^{(k+1)^2}\). 4. Therefore, the identity holds for every integer \(n\ge1\).

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

- 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)\).

- Determine the factor by which the power changes when the index increases by \(1\). - Rewrite the new expression using the previous one plus a constant remainder.

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

For every integer \(n\ge0\), \(7\mid(2^{3n}-1)\).

- Express the new quantity as a multiple of the previous one plus or minus a remainder. - Check whether that remainder has the required divisibility.

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

For every integer \(n\ge0\), \(3\mid(4^n+2)\).

- Compute the difference between the expressions at consecutive integers. - Look for a common factor in every term of that difference.

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

For every integer \(n\ge0\), \(6\mid(2n^3+3n^2+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}\).

- Verify the stated starting value carefully. - In the inductive step, compare only the new factorial factor with the growth factor on the right.

1. Base case: For \(n=4\), \(4!=24>16=2^4\). 2. Inductive hypothesis: Assume \(k!>2^k\) for an arbitrary integer \(k\ge4\). 3. Then \((k+1)!=(k+1)k!>(k+1)2^k\). 4. Since \(k+1>2\), \((k+1)!>2\cdot2^k=2^{k+1}\). 5. Therefore, the inequality holds for every integer \(n\ge4\).

For every integer \(n\ge4\), \(n!>2^n\).

- 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}\).

- Divide the larger polygon into a smaller polygon and a basic shape. - Determine how much the angle sum increases when one vertex is added.

1. Base case: A triangle has an interior-angle sum of \(180^\circ=(3-2)\cdot180^\circ\). 2. Inductive hypothesis: Assume a convex polygon with \(k\ge3\) vertices has interior-angle sum \((k-2)\cdot180^\circ\). 3. Add a new vertex outside one side so that the result is a convex polygon with \(k+1\) vertices. A diagonal joining the endpoints of the replaced side divides the new polygon into the original \(k\)-gon and a triangle. 4. Therefore, the interior-angle sum increases by \(180^\circ\): \((k-2)\cdot180^\circ+180^\circ=(k-1)\cdot180^\circ\). 5. This is the formula for \(k+1\), so it holds for every integer \(n\ge3\).

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

- 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.

- When adding a square, count the sides that disappear from the boundary and the sides that become visible. - Distinguish the total number added from the net increase.

1. Base case: For \(n=1\), the boundary consists of \(4=2\cdot1+2\) sides. 2. Inductive hypothesis: Assume the boundary of a row of \(k\ge1\) squares consists of \(2k+2\) square sides. 3. When one more square is attached, one previous boundary side becomes interior, while three new boundary sides appear. The net increase is \(2\) sides. 4. The new boundary has \(2k+2+2=2(k+1)+2\) square sides. 5. Therefore, the boundary consists of \(2n+2\) square sides for every integer \(n\ge1\).

For every integer \(n\ge1\), the boundary consists of \(2n+2\) square sides.

- Determine how the constant factor changes with each derivative. - Treat the function itself as the zeroth derivative.

1. Base case: For \(n=0\), \(f^{(0)}(x)=f(x)=e^{2x}=2^0e^{2x}\). 2. Inductive hypothesis: Assume \(f^{(k)}(x)=2^ke^{2x}\) for an arbitrary integer \(k\ge0\). 3. Differentiate: \(f^{(k+1)}(x)=2^k\cdot2e^{2x}=2^{k+1}e^{2x}\). 4. Therefore, the formula holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(f^{(n)}(x)=2^ne^{2x}\).

- 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}\).

- 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\).

- Factor the difference of squares in the new factor. - Cancel common factors before comparing the result with the target form.

1. Base case: For \(n=2\), the left side is \(1-\frac14=\frac34\), and the right side is \(\frac{2+1}{2\cdot2}=\frac34\). 2. Inductive hypothesis: 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+1)^2-1}{(k+1)^2}=\frac{k(k+2)}{(k+1)^2}\). 4. Therefore, \(\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 for \(k+1\), so the identity holds for every integer \(n\ge2\).

For every integer \(n\ge2\), \(\prod_{j=2}^{n}\left(1-\frac{1}{j^2}\right)=\frac{n+1}{2n}\).

- 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\).

- In the inductive step, compare the factor \(4\) with the growth from one cube to the next. - Check the remaining inequality at the smallest allowed index.

1. Check the initial values: \(4^0=1\ge0^3\), \(4^1=4\ge1^3\), and \(4^2=16\ge2^3\). 2. Inductive hypothesis: Assume \(4^k\ge k^3\) for an arbitrary integer \(k\ge2\). 3. Then \(4^{k+1}=4\cdot4^k\ge4k^3\). 4. For \(k\ge2\), \(4k^3-(k+1)^3=(k-2)(3k^2+3k+3)+5>0\). Thus, \(4k^3>(k+1)^3\), so \(4^{k+1}\ge(k+1)^3\). 5. Together with the separately checked cases \(n=0\) and \(n=1\), the inequality holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(4^n\ge 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\).

- After applying the inductive hypothesis, compare two quadratic expressions. - Determine the first index at which the comparison is strict.

1. Check the initial values: \(3^0=1>0^2\), \(3^1=3>1^2\), and \(3^2=9>2^2\). 2. Inductive hypothesis: Assume \(3^k>k^2\) for an arbitrary integer \(k\ge2\). 3. Then \(3^{k+1}=3\cdot3^k>3k^2\). 4. For \(k\ge2\), \(3k^2-(k+1)^2=2k^2-2k-1=2k(k-1)-1>0\). Thus, \(3k^2>(k+1)^2\), so \(3^{k+1}>(k+1)^2\). 5. Together with the separately checked cases \(n=0\) and \(n=1\), the inequality holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(3^n>n^2\).

- 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\).

- Differentiation produces two terms with the same exponential factor. - Compare the linear factor before and after differentiating.

1. Base case: For \(n=0\), \(f^{(0)}(x)=f(x)=(x+0)e^x\). 2. Inductive hypothesis: Assume \(f^{(k)}(x)=(x+k)e^x\) for an arbitrary integer \(k\ge0\). 3. Using the product rule, \(f^{(k+1)}(x)=e^x+(x+k)e^x=(x+k+1)e^x\). 4. This is the formula for \(k+1\), so it holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(f^{(n)}(x)=(x+n)e^x\).

- 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: For \(n=1\), exactly \(1=2^1-1\) move is necessary and sufficient. 2. Inductive hypothesis: Assume that moving \(k\ge1\) disks requires at least \(2^k-1\) moves and can be completed in exactly that many moves. 3. To move \(k+1\) disks, the top \(k\) disks must first be moved to the auxiliary peg, then the largest disk must be moved, and finally the \(k\) disks must be moved onto it. Thus, at least \((2^k-1)+1+(2^k-1)=2^{k+1}-1\) moves are necessary. 4. By the inductive hypothesis, each of the two \(k\)-disk subproblems can be completed in exactly \(2^k-1\) moves. Therefore, the total of \(2^{k+1}-1\) moves is achievable. 5. Hence, the minimum number of moves is exactly \(2^n-1\) for every integer \(n\ge1\).

For \(n\ge1\) disks, the minimum number of moves is exactly \(2^n-1\).

- 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. - After expanding, identify the nonnegative extra term.

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

For every integer \(n\ge0\) and every real number \(x\ge-1\), \((1+x)^n\ge1+nx\).

- 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}\).

- Compare a polygon with another polygon that has exactly one additional vertex. - Count the new connections and the old side whose role changes.

1. Base case: A triangle has \(0=\frac{3\cdot(3-3)}{2}\) diagonals. 2. Inductive hypothesis: Assume a convex polygon with \(k\ge3\) vertices has \(\frac{k(k-3)}{2}\) diagonals. 3. Add a new vertex outside one side so that the result is a convex polygon with \(k+1\) vertices. The new vertex creates \(k-2\) new diagonals. In addition, the side that was replaced becomes a diagonal of the new polygon. Thus, the number of diagonals increases by \(k-1\). 4. The new total is \(\frac{k(k-3)}{2}+k-1=\frac{(k+1)(k-2)}{2}\), which is the formula for \(k+1\). 5. Therefore, every convex polygon with \(n\ge3\) vertices has exactly \(\frac{n(n-3)}{2}\) diagonals.

A 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}\).

- Differentiate the polynomial factor and the exponential factor separately. - Then group terms by powers of \(x\). - Compare the constant terms for consecutive indices.

1. Base case: For \(n=0\), the formula gives \(f^{(0)}(x)=x^2e^x\). 2. Inductive hypothesis: Assume \(f^{(k)}(x)=\left(x^2+2kx+k(k-1)\right)e^x\) for an arbitrary integer \(k\ge0\). 3. Using the product rule, \(f^{(k+1)}(x)=\left(2x+2k+x^2+2kx+k(k-1)\right)e^x\). 4. Combine like terms: \(f^{(k+1)}(x)=\left(x^2+2(k+1)x+k(k+1)\right)e^x\). 5. This is the formula for \(k+1\), so it holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(f^{(n)}(x)=\left(x^2+2nx+n(n-1)\right)e^x\).

- Compare the expressions for consecutive indices. - A simpler divisibility result may be enough for the remaining difference.

1. Base case: For \(n=0\), \(4^0+24\cdot0-1=0\), which is divisible by \(9\). 2. Inductive hypothesis: Assume \(4^k+24k-1\) is divisible by \(9\) for an arbitrary integer \(k\ge0\). 3. The expression for \(k+1\) equals the expression for \(k\) plus \(3\cdot4^k+24=3(4^k+8)\). 4. Since \(4\equiv1\pmod{3}\), \(4^k\equiv1\pmod{3}\). Therefore, \(4^k+8\) is divisible by \(3\), so \(3(4^k+8)\) is divisible by \(9\). 5. Thus, the expression for \(k+1\) is divisible by \(9\), and the statement holds for every integer \(n\ge0\).

For every integer \(n\ge0\), \(9\mid(4^n+24n-1)\).