Skip to main content

Constrained Counting and Recurrence Workshop

Attempt P6–P11 after lessons 5–9. Feedback follows your saved attempt. Treat coefficient extraction as a proof-backed counting method.

  1. P6: Count nonnegative solutions to x+y+z=7 with each variable at most 3. Solve by inclusion-exclusion and by listing solution types. Explain why ordinary stars and bars alone overcounts.
  2. P7: Prove two of any 13 integers have equal remainder modulo 12. Then prove some server receives at least three of seven tasks assigned to three servers. State what these existence results do not count.
  3. P8: Derive the recurrence for binary words without adjacent ones, including the empty word. Compare with tilings by lengths 1 and 2. State the index shift needed for a bijection and give forward/inverse constructions.
  4. P9: Solve aₙ=3aₙ₋₁+2 with a₀=1. Verify the formula by induction, not just the first few values. Explain why arbitrary recurrences need not have a convenient characteristic-root solution.
  5. P10: Count unordered coin multisets totaling four with denominations 1 and 2. Compare with ordered sequences of 1s and 2s totaling four. Derive both generating functions and explain their difference.
  6. P11: For A(x)=Σaₙxⁿ, find coefficients of xⁿ in xA(x), A(x)/(1−x), and xA′(x). Explain the size shift in A′(x) alone. Give a finite-coefficient computation that does not evaluate the series at a real number.