1. Prove by induction that it is possible to pay, without requiring change, any whole number of roubles greater than 7 with banknotes of value 3 roubles and 5 roubles.

2. Prove by induction that _r=1Σⁿ r² = (1/6) (n +1) (2n + 1).

Deduce formulae for

1·1 +2·3 + 3·5 + 4·7 + ········ + n (2n- 1) and 1² + 3² + 5²+ · · · · ·  (2n-1)².

3. Here is another way to work out _r=1Σⁿ r². Observe that (r+ 1)³ - r³ = 3r² + 3r + 1. Hence

_r=1Σⁿ r²(r+ 1)³ - r³ = 3 _r=1Σⁿ r² +3 _r=1Σⁿ r + n

The left-hand side is equal to

(2³ - 1³) + (3³ -2³) + (4³ -3³) +······ + ((n +1)³ -n³) = (n +1)³ -1. Hence we can work out _r=1Σⁿ r².

Carry out this calculation, and check that your formula agrees with that in Exercise 2.

Use the same method to work out formulae for _r=1Σⁿ r³ and _r=1Σⁿ r⁴.

4. Prove the following statements by induction:

(a) For all integers n ≥ 0, the number 5²ⁿ- 3ⁿ is a multiple of 11.

(b) For any integer n ≥ 1, the integer 2⁴ⁿ-1 ends with an 8.

(c) The sum of the cubes of three consecutive positive integers is always a multiple of 9.

(d) If x ≥ 2 is a real number and n ≥1I is an integer, then xⁿ ≥ nx.

(e) If n > 3 is an integer, then 5ⁿ > 4ⁿ + 3ⁿ + 2ⁿ.

5. a) Factorize x^{2n +1} - 1 as a product of real linear and quadratic polynomials.

(b) Write x²ⁿ + x^2n-1 + ······ x + 1 as a product of real quadratic polynomials.

(c) Let ω = e ^{(2Πi) / (2n +1)+1}. Show that Σ ω^i+j = 0, where the sum is over all I and j from1 to 2n + 1 such that i < j.

6. Here is a "proof" by induction that any two positive integers are equal (e.g., 5 = 10):

First, a definition: if a and b are positive integers, define max (a, b) to be the larger of a and b if a ≠ b, and to be a if a = b. [For instance, max (3, 5) = 5, max (3, 3) = 3.] Let P (n) be the statement: "if a and b are positive integers such that max (a, b) = n, then a = b." We prove P (n) true for all n > 1 by induction. [As a consequence, if a, b are any two positive integers, then a = b, since P (n) is true, where it = max (a, b).] First, P (1) is true, since if max (a, b) = 1 then a and b must both be equal to I. Now assume P (n) true. Let a, b be positive integers such that max (a, b) = n + 1. Then max (a - 1, b - 1) = n. As we are assuming P (n), this implies that a - 1 = b - 1, hence a = b. Therefore, P (n + I) is true. By induction, P (n) is true for all n.

There must be something wrong with this "proof" Can you find the error?