Example 1.5.1. We know that every polynomial in SI: is a linear combination of 1, 3:, $2, $3, . . . . We use strong induction to prove the statement that every polynomial is a linear combination of l,(m1),(:r1)2,($ 1)3,.... Let P(n) be the statement that every polynomial of degree n is a linear combination of powers of :19 1. Then P(0) is true: the only polynomials of degree 0 are constants, and we can write (3 : c ' 1. Now assume that P(0), P(1), . . . , P(n) are all true. We will use them to show that P(n+1) is true. Let f (:13) be an arbitrary polynomial of degree n + 1. Let a be its leading coefcient so that f(.7:) : amn +- ~ ~ and dene 9(53) : x) a~ (a: 1)"+1. Then g(:r) is a polynomial of degree 3 77. since we have canceled off the mm\" terms. So by strong induction, g(m) is a linear combination of powers of :1: 1. If we add a - (.7: 1)\"+1 to this linear combination, we see that x) is also a linear combination of powers of m 1. Since our argument applies to any polynomial of degree n + 1, we have proved P(n + l) is true. Some examples to think about: 0 Every positive integer can be written in the form 2\"m where n 2 0 and m is an odd integer. 0 Every integer n 2 2 can be written as a product of prime numbers. 0 Dene a function f on the natural numbers by f(0) : 1, f(1) = 2, and f(n + 1) : f(n 1) + 2f(n) for all n 2 1. Show that f(n) g 3\" for all n 2 O. o A chocolate bar is made up of unit squares in an n X m rectangular grid. You can break up the bar into 2 pieces by breaking on either a horizontal or vertical line. Show that you need to make nm 1 breaks to completely separate the bar into 1 X 1 squares (if you have 2 pieces already, stacking them and breaking them counts as 2 breaks). The bottomline is that both forms of induction are valid and it's ne to use whatever makes the most sense in context. (2) Let's change Example 1.5.1 a little bit: we want to Show that every polynomial in st can be written as a linear combination of powers of 2a: 1: 1, 2x 1, (2s: 1)2, (22: 1)3, (2x 1)4, . . .. The same proof almost works; explain what needs to be changed (you don't need to rewrite the whole proof)