1. In a proof by induction, what is the purpose of the base case?

A. To prove the statement for all values at once B. To assume the statement is true for some n C. To verify the statement is true for the initial value, typically \( n = 0 \) or \( n = 1 \) D. To prove the statement for \( n+1 \) directly

2. What operation in the MU Puzzle directly shortens the string?

A. Doubling the contents after M B. Replacing III with U C. Removing any UU D. Appending U if the string ends in I

3. Which of the following demonstrates a correct inductive argument start?

A. Suppose the statement is true for some n B. Show the statement for n+1 implies it is true for n C. Prove the base case (often n=0 or n=1) is true D. Assume the statement is false and derive a contradiction

4. Why is it impossible to produce MU from MI in the MU Puzzle?

A. Because rules do not allow letter additions B. Because the number of I's must become a multiple of three, which cannot happen C. Because the letter U is not present initially D. Because the string length cannot increase

5. In the inductive step, which assumption is made?

A. The statement is true for all values except \( n \) B. The statement is true for \( n+1 \) C. The statement is true for an arbitrary \( n \) D. The statement is false for \( n \)

6. In the MU Puzzle, which letter must the number of I’s be a multiple of to make MU?

A. 2 B. 3 C. 4 D. 5

7. The series 2^0 + 2^1 + 2^2 + ... + 2^n equals which of the following?

A. 2^(n+1) B. 2^(n+1) - 1 C. n * 2^n D. 2^n - 1

8. Which operation can only be applied if the string ends in an I?

A. Remove any UU B. Append U to the string C. Replace III with U D. Double the contents after M

9. What kind of proofs become less formal as familiarity with induction grows?

A. Proofs with clear base cases and induction steps B. Proofs without base cases C. Proofs without inductive hypotheses D. Proofs by contradiction without examples

10. How many coins can be tested with two weighings to find one heavier counterfeit coin?

A. 3 B. 6 C. 9 D. 12

11. When taking larger steps in induction, what is usually done?

A. Prove multiple cases at once to advance the argument B. Skip the inductive step for certain numbers C. Only prove the base case D. Use geometric progressions instead of arithmetic ones

12. Why is the inductive step important in a proof by mathematical induction?

A. It verifies the base case B. It demonstrates the property holds for all cases by linking n to n+1 C. It defines the property to be proven D. It provides an example counterexample

13. In the coin weighing problem, what assumption is made about the counterfeit coin?

A. It weighs less than the genuine coins B. It weighs more than the genuine coins C. It can weigh either more or less D. Its weight is irrelevant as long as it differs

14. What pattern emerges in the counterfeit coin problem for n weighings?

A. The maximum number of coins is n+1 B. The maximum number of coins is 2n C. The maximum number of coins is 3^n D. The maximum number of coins doubles every weighing

15. What is the maximum number of coins for which a single weighing on a balance can find the counterfeit coin?

A. 1 B. 2 C. 3 D. 4

16. In the context of induction, what does "starting induction later" refer to?

A. Starting the base case at a number greater than zero B. Delaying the induction step until the conclusion is reached C. Beginning with the largest number in a domain D. Skipping the base case entirely

17. In the MU Puzzle, what base string do the rules start with?

A. M B. IU C. MI D. MU

18. What does the formula \( \sum_{i=0}^3 2^i = 2^0 + 2^1 + 2^2 + 2^3 \) evaluate to?

A. 8 B. 15 C. 16 D. 7

19. The phrase "Starting induction later" in variations on induction means:

A. Beginning induction at a base case other than zero or one B. Delaying induction until after the problem is solved C. Skipping the base case D. Beginning at n=0 only

20. In an induction proof, why must both the base case and inductive step be valid?

A. To ensure the statement holds for a single value only B. To guarantee the property holds for all natural numbers starting from base C. To find counterexamples D. To avoid proving anything

21. Which of the following best exemplifies the formula for summation from 1 to \( n \)?

A. \( \sum_{i=1}^n i = \frac{n(n+1)}{2} \) B. \( \sum_{i=1}^n i = n^2 \) C. \( \sum_{i=1}^n i = n + 1 \) D. \( \sum_{i=1}^n i = \frac{n}{2} \)

22. What is often the starting point in summation examples given?

A. \( i = 0 \) or \( i=1 \) B. \( i = 3 \) C. \( i = n \) D. \( i = -1 \)

23. What logical insight does the MU Puzzle demonstrate about the possibility of transforming MI into MU?

A. The string length always doubles B. The number of U's remains constant C. The number of I's will never become a multiple of three D. The string cannot be shortened once it grows

24. Complete induction is introduced as a variation on which broader mathematical principle?

A. Double counting B. Mathematical induction C. Direct proof D. Contradiction

25. What kind of mathematical proof is introduced as "variations on induction"?

A. Proof by contradiction B. Direct proof only C. Modified induction techniques like complete induction and larger steps D. Graph-based proofs

26. What is the typical starting point \( P(n) \) in a standard induction proof?

A. \( n = -1 \) B. \( n = 1 \) or \( n=0 \) C. \( n = 10 \) D. \( n \) arbitrary natural number

27. Which of the following describes the structure of a proof by induction?

A. Base case, test all values, conclusion B. Base case, inductive hypothesis, inductive step, conclusion C. Assume conclusion, prove base case, conclude D. Prove directly with examples

28. What is illustrated by the progression where with two weighings you can identify a counterfeit coin among 9 coins?

A. Linear increase with weighings B. Exponential growth of possibilities based on weighings C. Decrease in error probability D. Arithmetic progression in coin count

29. In mathematical induction, the phrase "state your choice of \( P(n) \)" means:

A. Choose a random property B. Define the property or statement you want to prove for all \( n \) C. Choose \( n \) arbitrarily D. Choose the base case value

30. Why is mathematical induction considered a powerful proof technique?

A. Because it proves all cases simultaneously B. Because it avoids the need for examples C. Because it allows proving infinitely many cases through a base case and an inductive step D. Because it only applies to natural numbers

31. When given two weighings on a balance, what is the maximum number of coins among which you can identify one counterfeit coin heavier than the others?

A. 3 B. 6 C. 9 D. 12

32. What is a characteristic of complete induction compared to regular induction?

A. It starts at zero always B. It examines multiple previous cases to prove the next case C. It only works for finite sets D. It does not require a base case

33. The pattern described where with 0 weighings one can find the counterfeit coin among 1 coin, with 1 weighing among 3 coins, and with 2 weighings among 9 coins illustrates which mathematical concept?

A. Arithmetic sequence B. Geometric sequence based on powers of 3 C. Fibonacci sequence D. Exponential base 2 growth

34. If in the MU Puzzle the number of I’s is never a multiple of three, what does this imply?

A. The string MU can eventually be formed B. The transformation from MI to MU is impossible C. The number of U's will increase indefinitely D. The string length will stay constant

35. What is the key observation about the number of I's in the MU Puzzle?

A. The number of I's is always even B. The number of I's is always a prime number C. Initially, the number of I's is not a multiple of three D. The number of I's always starts as a multiple of three

36. In the MU Puzzle, what is the significance of the number of I's in the string?

A. It determines if the string ends with a U B. It controls which operations can be applied next C. It must be a multiple of three to get the string MU D. It determines the length of the string after doubling

37. In the Counterfeit Coin Problem, with one weighing, what is the maximum number of coins in which you can find the counterfeit coin?

A. 1 B. 2 C. 3 D. 4

38. If a property holds for \( n=0 \) and \( P(n) \Rightarrow P(n+1) \), which proof technique is being used?

A. Complete Induction B. Proof by Contradiction C. Mathematical Induction D. Direct Proof

39. According to the MU Puzzle rules, what happens when you apply the operation "replace III with U"?

A. The string gets longer by three characters B. The string is shortened by two characters C. Three consecutive I's are replaced by one U D. One U transforms back into three I's

40. The MU Puzzle begins with the string "MI". What operation can generate "MII" from "MI"?

A. Doubling the contents after M B. Replacing III with U C. Removing UU D. Appending U since the string ends in I

41. What is the foundational concept behind mathematical induction?

A. Proving a statement true for all real numbers B. Proving a statement true for all natural numbers by showing a base case and an inductive step C. Estimating sums using limits D. Testing statements for specific values only

42. Which problem-solving approach is used to find the counterfeit among coins?

A. Recursive partitioning B. Exhaustive search C. Divide and conquer with weighings D. Random selection

43. Which of the following best describes the key challenge in the MU Puzzle?

A. Finding the shortest string that transforms MI to MU B. Determining if the number of I's can ever become a multiple of three C. Counting the number of U's in each string D. Doubling the entire string repeatedly

44. What does "complete induction" (strong induction) allow you to assume when proving \( P(n+1) \)?

A. \( P(0) \) only B. \( P(k) \) for all \( k \leq n \) C. \( P(n) \) only D. \( P(n-1) \) only

45. Why is the example "How Not To Induct" important?

A. Shows how to skip the base case B. Shows that incorrect assumptions invalidate induction C. Shows a simplified induction method D. Shows an example with complex summations

46. To complete an induction proof, what must be shown after assuming \( P(n) \)?

A. That \( P(0) \) is true B. That \( P(n) \) implies \( P(n+1) \) is true C. That \( P(k) \) for some \( k < n \) is true D. That the statement is false for \( n+1 \)

47. When proving \( P(n + 1) \) from the inductive hypothesis, what is the main goal?

A. To prove the base case again B. To prove \( P(n + 1) \) assuming \( P(n) \) is true C. To use contradiction to show \( P(n+1) \) cannot be false D. To find a counterexample

48. What signifies the inductive hypothesis in an induction proof?

A. Assuming \( P(n) \) is false for a specific \( n \) B. Assuming \( P(n) \) is true for an arbitrary \( n \) C. Proving \( P(0) \) directly D. Disproving \( P(n-1) \)

49. Which problem-solving approach uses induction to find the counterfeit coin?

A. Binary search B. Divide and conquer based on powers of 3 C. Random guessing D. Linear search

50. In the summation \( \sum_{i=0}^2 (i^2 - i) \), what is the evaluated sum?

A. 2 B. 3 C. 4 D. 5