SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Proof, EXT2 P2 2018 HSC 16a

Use mathematical induction to prove that, for  `n >= 1`,

`x^((3^n)) - 1 = (x - 1)(x^2 + x + 1)(x^6 + x^3 + 1) … (x^((2 xx 3^(n - 1))) + x^((3^(n - 1))) + 1)`.  (3 marks)

Show Answers Only

`text(See Worked Solutions)`

Show Worked Solution

`text(If)\ \ n = 1`

♦ Mean mark 51%.

`text(LHS) = x^3 – 1`

`text(RHS)` `=(x-1)(x^2+x+1)`  
  `=x^3+x^2+x-x^2-x-1`  
  `=x^3-1 = text(LHS)`  

 
`:.\ text(True for)\ n = 1`
 

`text(Assume true for)\ \ n = k`

`x^(3^k) – 1 = (x – 1)(x^2 + x + 1) … (x^(2 xx 3^(k – 1)) + x^(3^(k – 1)) + 1)`

 
`text(Prove true for)\ \ n = k + 1`

`text(i.e.)\ \ \ x^(3^(k + 1)) = underbrace{(x – 1)(x^2 + x + 1) …(x^(2 xx 3^(k – 1)) + x^(3^(k – 1)) + 1)}_{x^(3^k) – 1) (x^(2 xx 3^k) + x^(3^k) + 1)`

`x^(3^(k + 1)) – 1` `= (x^(3^k) – 1)(x^(2 xx 3^k) + x^(3^k) + 1)`
  `= x^(3 xx 3^k) + x^(2 xx 3^k) + x^(3^k) – x^(2 xx 3^k) – x^(3^k) – 1`
  `= x^(3^(k + 1)) – 1`

 
`=>\ text(True for)\ \ n = k + 1`

`:.\ text(S)text(ince true for)\ \ n = 1,\ text(by PMI, true for integral)\ \ n >= 1.`

Proof, EXT2 P2 2017 HSC 16c

A 2 by `n` grid is made up of two rows of `n` square tiles, as shown.
 

The tiles of the 2 by `n` grid are to be painted so that tiles sharing an edge are painted using different colours. There are `x` different colours available, where  `x ≥ 2`.

It is NOT necessary to use all the colours.

Consider the case of the 2 by 2 grid with tiles labelled A, B, C and D, as shown.
 

There are `x(x - 1)` ways to choose colours for the first column containing tiles A and B. Do NOT prove this.

  1. Assume the colours for tiles A and B have been chosen. There are two cases to consider when choosing colours for the second column. Either tile C is the same colour as tile B, or tile C is a different colour from tile B.

     

    By considering these two cases, show that the number of ways of choosing colours for the second column is  `x^2 - 3x +3`.  (2 marks)

  2. Prove by mathematical induction that the number of ways in which the 2 by `n` grid can be painted is  `x(x - 1)(x^2 - 3x + 3)^(n - 1)`, for  `n ≥ 1`.  (2 marks)

  3. In how many ways can a 2 by 5 grid be painted if 3 colours are available and each colour must now be used at least once?  (2 marks)

Show Answers Only
  1. `text(See Worked Solutions)`
  2. `text(See Worked Solutions)`
  3. `480`
Show Worked Solution
i.   

`text(If Colour)\ C =\ text(Colour)\ B:`

♦♦♦ Mean mark 20%.

`text(Column 2 combinations)`

`= 1 xx (x – 1)`

`= x – 1`

 

`text(If Colour)\ C !=\ text(Colour)\ B:`

`text(Column 2 combinations)`

`= (x – 2)(x – 2)`

 

`:.\ text(Total number of ways for column 2)`

`= x – 1 + (x – 2)^2`

`= x^2 – 3x + 3\ \ …\ text(as required.)`

 

ii.   `P(n) = x(x – 1)(x^2 – 3x + 3)^(n – 1)`

♦♦♦ Mean mark 22%.

`text(If)\ \ n = 1\ \ (text(i.e. 1 column)),`

`text(Combinations) = x(x – 1)\ \ (text(given))`

`P(1)` `= x(x – 1)(x^2 – 3x + 3)^0`
  `= x(x – 1)`

`:. text(True for)\ n = 1`

 

`text(Assume true for)\ n = k:`

`text(i.e. Possible combinations for)\ k\ text(columns)`

`P(k) = x(x – 1)(x^2 – 3x + 3)^(k – 1)`

`text(Prove true for)\ \ n = k + 1`

`text(i.e.)\ \ P(k + 1) = x(x – 1)(x^2 – 3x + 3)^k`

 

`text(Consider a grid)\ 2 xx k\ text(and add an extra two)`

`text(tiles to make a)\ 2 xx (k + 1)\ text(grid.)`

`text(Total possible combinations)`

`= text(combinations of)\ (2 xx k)\ text(grid) xx (x^2 – 3x + 3)\ \ (text{from (i)})`

`= x(x – 1)(x^2 – 3x + 3)^(k – 1) xx (x^2 – 3x + 3)`

`= x(x – 1)(x^2 – 3x + 3)^k`

`=> text(True for)\ \ n = k + 1`

`:. text(S)text(ince true for)\ n = 1,\ text(by PMI, true for integral)\ n >= 1.`

 

iii.   `text(If)\ \ n = 5, \ x = 3:`

♦♦♦ Mean mark 22%.

`text{Total combinations (includes using only 2 colours)}`

`P(5)` `= 3(3 – 1)(3^2 – 3.3 + 3)^4`
  `= 3(2)(3)^4`
  `= 486`

 

`text(Consider pattern when only 2 colours used:)`

`text(Combinations that only use 2 colours)`

`=\ text(Colours in box 1 × possible colours in box 2)`

`= 3 xx 2`

`= 6`

`:.\ text(Combinations if each colour used at least once)`

`= 486 – 6`
`= 480`

Proof, EXT2 P2 2016 HSC 16c

In a group of `n` people, each has one hat, giving a total of `n` different hats. They place their hats on a table. Later, each person picks up a hat, not necessarily their own.

A situation in which none of the `n` people picks up their own hat is called a derangement.

Let  `D(n)`  be the number of possible derangements.

  1. Tom is one of the `n` people. In some derangements Tom finds that he and one other person have each other's hat.

     

    Show that, for  `n > 2`, the number of such derangements is  `(n - 1) D (n - 2).`  (1 mark)

  2. By also considering the remaining possible derangements, show that, for  `n > 2,`

    `qquad qquad D(n) = (n - 1) [D(n - 1) + D(n - 2)].`  (2 marks)

  3. Hence, show that  `D(n) - nD(n - 1) = -[D(n - 1) - (n - 1) D(n - 2)]`,  for  `n > 2.`  (1 mark)

  4. Given  `D(1) = 0`  and  `D(2) = 1`,  deduce that  `D(n) - n D(n - 1) = (-1)^n`,  for  `n > 1.`  (1 mark)

  5. Prove by mathematical induction, or otherwise, that for all integers  `n >= 1,\ D(n) = n! sum_(r = 0)^n (-1)^r/(r!).`  (2 marks)

Show Answers Only
  1. `text(See Worked Solutions)`
  2. `text(See Worked Solutions)`
  3. `text(See Worked Solutions)`
  4. `text(See Worked Solutions)`
  5. `text(See Worked Solutions)`
Show Worked Solution

i.   `text(Tom and one other person can have each)`

♦♦♦ Mean mark 22%.

`text(other’s hat in)\ (n – 1)\ text(combinations.)`

`text(There are)\ \ D(n – 2)\ \ text(possibilities for the)`

`text(rest of the people selecting the wrong hats.)`

`:. text(Number of derangements) = (n – 1)D(n – 2)`

 

ii.   `text(Consider all possible derangements:)`

♦♦♦ Mean mark 6%.

`text(Any of)\ n\ text(people choose the wrong hat.)`

`text(Remainder)\ (n – 1)\ text(people can select the)`

`text(wrong hat in)\ D(n – 1)\ text(ways.)`

`:. nD(n – 1)\ text(derangements.)`

`text{This includes part (i) combinations.}`

 

`:.\ text(Remaining possible derangements)`

`= nD(n – 1) – (n – 1)D(n – 2)`

`= nD(n – 1) – D(n – 1)`

`= (n – 1)D(n – 1)`

`:. D(n)` `= (n – 1)D(n – 1) + (n – 1)D(n – 2)`
  `= (n – 1)[D(n – 1) + D(n – 2)]`

 

♦♦ Mean mark part (iii) 37%.
iii.    `D(n)` `= (n – 1)[D(n – 1) + D(n – 2)]`
    `= nD(n – 1) – D(n – 1) + (n – 1)D(n – 2)`

 

`:. Dn – nD(n – 1) = −[D(n – 1) – (n – 1)D(n – 2)]`

 

iv.   `D(1) = 0, D(2) = 1`

♦♦♦ Mean mark 1%!

`D(2) – 2D(1) = 1`

`D(3) – 3D(2) = −[D(2) – 2D(1)] = −1`

`D(4) – 4D(3) = −[D(3) – 3D(2)] = −(−1) = 1`

`D(5) – 5D(4) = −[D(4) – 4D(3)] = −1`

 

`:. D(n) – nD(n – 1) = (−1)^n\ text(for)\ n > 1`

 

v.   `text(Prove)\ D(n) = n! sum_(r = 0)^n ((−1)^r)/(r!)\ text(for)\ n >= 1`

`text(When)\ n = 1,`

`D(1) = 1! sum_(r = 0)^1 ((−1)^r)/(r!) = 1 – 1 = 0`

`text(S)text(ince)\ D(1) = 0\ (text(given)),`

`:.\ text(True for)\ n = 1`

♦♦♦ Mean mark 13%.

 

`text(Assume true for)\ \ n = k,`

`text(i.e.)\ \ D(k) = k! sum_(r = 0)^k ((−1)^r)/(r!)`

`text(Prove true for)\ \ n=k+1,`

`text(i.e.)\ \ D(k+1) = (k+1)!sum_(r = 0)^(k+1) ((−1)^r)/(r!)`

`D(k+1)`

`= (k + 1)D(k) + (−1)^(k + 1)qquad(text{from part (iv)})`
`= (k + 1) · k! sum_(r = 0)^k ((−1)^r)/(r!) + (−1)^(k + 1)`
`= (k + 1)!(1 – 1/(1!) + 1/(2!) – 1/(3!) + … + ((−1)^k)/(k!)) + (−1)^(k + 1) · ((k + 1)!)/((k + 1)!)`
`= (k + 1)!(1 – 1/(1!) + 1/(2!) – 1/(3!) + … + ((−1)^k)/(k!) + ((−1)^(k+1))/((k+1)!))`
`= (k + 1)! sum_(r = 0)^(k + 1) ((−1)^r)/(r!)`

 

`=> text(True for)\ n = k + 1.`

`:. text(S)text(ince true for)\ \ n = 1,\ text(by PMI, true for integral)\ n >= 1.`

Proof, EXT2 P2 EQ-Bank 10

Use mathematical induction to prove that

`sum_(r=1)^n r^3 = 1/4 n^2 (n + 1)^2`

`text(for integers)\ n>=1`  (3 marks)

Show Answers Only

 `text(Proof)\ \ text{(See Worked Solutions)}`

Show Worked Solution

`text(Need to prove)\  sum_(r=1)^n r^3 = 1/4 n^2 (n + 1)^2\ \ text(integral)\ n>=1 `

`text(i.e.)\ 1^3 + 2^3 + 3^3 + … + n^3 = 1/4 n^2 (n + 1)^2`

`text(When)\ n = 1`

`text(LHS) = 1^3 = 1`

`text(RHS) = 1/4 1^2 (1 + 1)^2 = 1`

`:.\ text(True for)\ n = 1`

 
`text(Assume true for)\ n = k`

`text(i.e.)\ 1^3 + 2^3 + … + k^3 = 1/4 k^2 (k + 1)^2`

`text(Need to prove true for)\ n = k + 1`

`1^3 + 2^3 + … + k^3 + (k + 1)^3 = 1/4 (k + 1)^2 (k + 2)^2`

`text(LHS)` `= 1/4 k^2 (k + 1)^2 + (k + 1)^3`
  `= 1/4 (k + 1)^2 [k^2 + 4(k + 1)]`
  `= 1/4 (k + 1)^2 (k^2 + 4k + 4)`
  `= 1/4 (k + 1)^2 (k + 2)^2`
  `=\ text(RHS)`

 
`=>text(True for)\ n = k + 1`

`:.text(S)text(ince true for)\ n = 1,\ text(true for integral)\ n >= 1`