Invariants Math Example 1
Follow the full solution, then compare it with the other examples linked below.
Example 1
mediumA sequence starts at 1 and each term is 3 times the previous minus 2: \(a_{n+1} = 3a_n - 2\). Show that the quantity \(a_n - 1\) grows by a factor of 3 each step (i.e., \(a_n - 1 = 3^{n-1}(a_1 - 1)\) is an invariant structure).
Solution
- 1 Define \(b_n = a_n - 1\). Then \(b_{n+1} = a_{n+1} - 1 = (3a_n - 2) - 1 = 3a_n - 3 = 3(a_n-1) = 3b_n\).
- 2 So \(b_n\) forms a geometric sequence: \(b_n = b_1 \cdot 3^{n-1}\).
- 3 With \(a_1=1\): \(b_1 = 0\), so \(b_n = 0\) for all \(n\), meaning \(a_n = 1\) for all \(n\).
- 4 Invariant: if \(a_1=1\), the fixed point \(a=1\) is preserved.
Answer
\(a_n = 1\) for all \(n\); fixed point is an invariant
An invariant is a quantity that doesn't change under the transformation. Here \(a_n = 1\) is a fixed point of the recurrence — once there, the sequence stays.
About Invariants
Quantities or properties that remain unchanged during a process, operation, or transformation—values that stay the same no matter how the system is rearranged or acted upon.
Learn more about Invariants →More Invariants Examples
Example 2 hard
In a game, you can add 3 or subtract 5 from a number. Starting at 0, can you reach 1? Use an invaria
Example 3 mediumThe sum of digits of a number doesn't change modulo 9 when you add 9. Verify: 47 → 47+9=56. Is the d
Example 4 mediumShow that for any right triangle with legs (a, b) and hypotenuse (c), the quantity (a^2 + b^2 - c^2
Example 5 hardA 2×n grid of squares is colored with 2 colors. You repeatedly flip all colors in any row or column.