Given a sequence of non negative integers $\{ {a_r}\}$ show that

(i)     $\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$ where $x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \}$.

(ii)     $\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} }$.

Hence determine whether the base $3$ number $22010112200201$ is divisible by $8$.

(i)     $(x + 1)(\bmod x) \equiv 1(\bmod x)$     (M1)

${(x + 1)^r}(\bmod x)\left( { \equiv {1^r}(\bmod x)} \right) = 1(\bmod x)$     A1

$\sum\limits_{r - 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) \equiv \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$     AG

(ii)     METHOD 1

$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){3^{2r}}} }$     M1

$= \sum\limits_{r = 0}^n {({3^{2r + 1}}{a_{2r + 1}} + {3^{2r}}{a_{2r}})}$     M1A1

$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$     AG

METHOD 2

$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = 3{a_1} + {a_0} + 9(3{a_3} + {a_2}) +  \ldots  + {9^n}(3{a_{2n + 1}} + {a_{2n}})}$     A1

$= {a_0} + 3{a_1} + {3^2}{a_2} + {3^3}{a_3} +  \ldots  + {3^{2n + 1}}{a_{2n + 1}}$     M1A1

$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$     AG

[5 marks]

METHOD 1

using part (a) (ii) to separate the number into pairs of digits     (M1)

$22010112200201{\text{ }}({\text{base }}3) \equiv 8115621{\text{ }}({\text{base }}9)$     A1

using the sum of digits identity from part (a) (i)     (M1)

Note:     Award M1 if result from a(i) is used to show that the number is divisible by $2$, even if no other valid working given.

${\text{sum}} = 24$     A1

which is divisible by $8$     A1

hence $22010112200201$ (base $3$) is divisible by $8$

METHOD 2

$\sum\limits_{r = 0}^{13} {{a_r}{3^r}\sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}}){9^r}} }$     (M1)

$\equiv \sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}})(\bmod 8)}$     A1

$= {a_0} + 3{a_1} + {a_2} + 3{a_3} +  \ldots  + {a_{12}} + 3{a_{13}}(\bmod 8)$     M1

$= (1 + 3 \times 0 + 2 + 3 \times 0 +  \ldots  + 3 \times 2)(\bmod 8) \equiv 24(\bmod 8)$     A1

$\equiv 0$ OR divisible by $8$     A1

hence $22010112200201$ (base $3$) is divisible by $8$

[5 marks]

Total [10 marks]