smc-1019-10-Divisibility

Proof, EXT1 P1 2024 HSC 12d

Use mathematical induction to prove that \(2^{3 n}+13\) is divisible by 7 for all integers \(n \geq 1\). (3 marks)

--- 12 WORK AREA LINES (style=lined) ---

Show Answers Only

\(\text{Proof (See worked solutions)}\)

Show Worked Solution

\(\text{Prove}\ \ 2^{3 n}+13\ \ \text{is divisible by 7 for}\ \ n \geq 1.\)

\(\text {If}\ \ n=1:\)

\(2^{3 \times 1}+13=21=3 \times 7\)

\(\therefore \text { True for } n=1.\)

\(\text {Assume true for } n=k:\)

\(2^{3 k}+13=7P \ \text{(where \(P\) is an integer)}\)

\(\Rightarrow 2^{3k}=7 P-13\ \ldots\ (1)\)

\(\text {Prove true for}\ \ n=k+1:\)

	\(2^{3(k+1)}+13\)	\(=2^{3 k} \times 2^3+13\)
		\(=8\left(2^{3 k}\right)+13\)
		\(=8(7P-13)+13\ \ \text{(see (1) above)}\)
		\(=56 P-8 \times 13+13\)
		\(=7(8 P-13)\)

\(\Rightarrow \text { True for } n=k+1\)

\(\therefore\ \text{Since true for}\ \ n=1, \text{by PMI, true for integers}\ \ n \geqslant 1.\)

Proof, EXT1 P1 2022 HSC 12f

Use mathematical induction to prove that `15 ^(n)+6^(2n+1)` is divisible by 7 for all integers `n >= 0`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

`text{Proof (See Worked Solutions)}`

Show Worked Solution

`text{Prove}\ \ 15 ^(n)+6^(2n+1)\ \ text{is divisible by 7 for}\ \ n>=0`

`text{If}\ \ n=0:`

`15^0+6^1=7`

`:.\ text{True for}\ \ n=0`

`text{Assume true for}\ \ n=k`

`text{i.e.}\ \ 15^(k)+6^(2k+1)=7P\ \ text{(where}\ P\ text{is an integer)}`

`=>6^(2k+1)=7P-15^(k)\ \ …\ (1)`

`text{Prove true for}\ \ n=k+1`

`15^(k+1)+6^(2k+3)`	`=1515^(k)+6^26^(2k+1)`
	`=15*15^(k)+36(7P-15^(k))\ \ text{(see (1))}`
	`=1515^(k)+367P-36*15^(k)`
	`=367P-2115^(k)`
	`=7(36P-3*15^(k))\ \ text{(which is divisible by 7)}`

`=>\ text{True for}\ \ n=k+1`

`:.\ text{S}text{ince true for}\ \ n=0, text{by PMI, true for integers}\ \ n>=0`

Proof, EXT1 P1 2017 HSC 14a

Prove by mathematical induction that `8^(2n + 1) + 6^(2n − 1)` is divisible by 7, for any integer `n ≥ 1`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

`text(See Worked Solutions)`

Show Worked Solution

`text(Prove)\ \ 8^(2n + 1) + 6^(2n − 1)\ \ text(is divisible)`

`text(by 7 for integers)\ \ n >= 1`

`text(If)\ n = 1,`

`8^3 + 6^1 = 518 = 74 xx 7`

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

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

`text(i.e.)\ \ 8^(2k + 1) + 6^(2k – 1)`	`= 7P\ \ (text(where)\ P\ text(is an integer))`
`8^(2k + 1)`	`= 7P – 6^(2k – 1)`

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

`8^(2k + 3) + 6^(2k − 1)`	`= 64 · 8^(2k + 1) + 36*6^(2k – 1)`
	`= 64(7P – 6^(2k – 1)) + 36 · 6^(2k – 1)`
	`= 64 · 7P – 64 · 6^(2k – 1) + 36 · 6^(2k – 1)`
	`= 64 · 7P – 28 · 6^(2k – 1)`
	`= 7(64P – 4 · 6^(2k – 1))`

`…\ text(which is divisible by 7.)`

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

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

Proof, EXT1 P1 2007 HSC 4b

Use mathematical induction to prove that `7^(2n – 1) + 5` is divisible by 12, for all integers `n ≥ 1`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

`text{Proof (See Worked Solutions)}`

Show Worked Solution

`text(Prove)\ \ 7^(2n – 1) + 5\ \ text(is divisible by)\ 12,\ text(for)\ \ n ≥ 1`

`text(If)\ \ n = 1`

`7^(2 – 1) + 5 = 7 + 5 = 12\ \ \ text{(divisible by 12)}`

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

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

`text(i.e.)\ 7^(2k − 1) + 5`	`= 12text{N (N is an integer)}`
`7^(2k-1)`	`= 12text(N) – 5\ \ …\ (1)`

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

`7^(2(k + 1) − 1) + 5`	`= 7^(2k + 1) + 5`
	`= 7^2 · 7^(2k − 1) + 5`
	`= 49(12text(N) − 5) + 5\ \ \ text{(from (1) above)}`
	`= 49*12text(N) − 245 + 5`
	`= 49*12text(N) − 240`
	`= 12(49text(N) − 20)`

`…text(which is divisible by)\ 12`

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

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

Proof, EXT1 P1 SM-Bank 23

Prove by mathematical induction that `(3n + 1)7^n - 1` is divisible by 9 for integral `n >= 1`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

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

Show Worked Solution

`text(Prove)\ \ (3n + 1)7^n\ – 1\ \ text(is divisible)`

`text(by 9 for integers)\ n >= 1.`

`text(If)\ \ n = 1`

`(3n + 1)7^n\ – 1`	`= (3 xx 1 + 1)7^1\ – 1`
	`= 27`

`=>\ text(Divisible by 9)\ \ (27//9=3)`

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

IMPORTANT: In cases where substitution doesn’t work, remember that `f(k+1)-f(k)` can be used to illustrate divisibility as well (Tony Lantry special).

`text(i.e.)\ (3k + 1)7^k\ – 1 = 9P\ \ \ text{(} P\ text(integer) text{)}`

`f(k)`	`= (3k + 1)7^k\ – 1`
`f(k + 1)`	`= (3 (k + 1) + 1)7^(k+1)\ – 1`
	`= (3k + 4)7^(k+1)\ – 1`

`f(k + 1)\ – f(k)`

`= (3k + 4) 7^(k + 1)\ -1- [(3k + 1)7^k\ – 1]`

`= 3k * 7^(k + 1) + 4 * 7^(k + 1)\ – 1\ – [3k*7^k + 7^k\ – 1]`

`= 21k*7^k + 28*7^k\ – 1\ – 3k*7^k\ – 7^k + 1`

`= 18k*7^k + 27*7^k`

`= 9 (2k*7^k + 3*7^k)\ \ text{(divisible)}`

`text(S)text(ince)\ \ `	`f(k + 1)\ – f(k)\ text(is divisible by 9 and)`
	`\ \ \ \ \ \ f(k)\ text(is divisible by 9,)`

`=> f(k + 1)\ text(is divisible by 9)`

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

Proof, EXT1 P1 2014 HSC 13a

Use mathematical induction to prove that `2^n + (− 1) ^(n + 1)` is divisible by 3 for all integers `n >= 1`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

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

Show Worked Solution

`text(Prove)\ \ 2^n + (-1)^(n + 1)`

`text(is divisible by 3 for integers)\ n >= 1`

`text(If)\ n = 1`

`2^1 + (-1)^2`	`= 2 + 1`
	`= 3\ \ text{(which is divisible by 3)}`

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

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

`text(i.e.)\ \ \ 2^k + (-1)^(k + 1)`	`= 3P\ text{(} P\ text(integer) text{)}`
`2^k`	`= 3P\ – (-1)^(k + 1)\ \ \ \ \ … \ text{(∗)}`

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

`2^(k + 1) + (-1)^(k + 1 + 1)`	`= 2*2^k + (-1)^(k + 2)`
	`= 2 (3P\ – (-1)^(k + 1)) + (-1)^(k + 2)\ \ text(… from)\ text{(∗)}`
	`= 6P\ – 2 (-1)^(k + 1)\ – 1 (-1)^(k + 1)`
	`= 6P\ – 3 (-1)^(k + 1)`
	`= 3 (2P\ – (-1)^(k + 1))`
`text(… which is divisible by 3)`

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

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

♦ Mean mark 51%.
IMPORTANT: Making `47^k` the subject helps the substitution in the proof for `n+1`. Students must state that `P` is an integer. NOTE: using `147^k=147xx147^(k-1)` develops proof for `n=k+1`.

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

`text(i.e.)\ 47^k + 53 xx 147^(k – 1) = 100P\ \ \ text{(} P\ text(integer) text{)}`

`47^k = 100P\ – (53 xx 147^(k – 1))\ \ \ text(…)\ text{(1)}`

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

`47^(k + 1) + 53 xx 147^(k)`

`= 47 xx 47^k + 53 xx 147^k`

`text{(substitute from (1) above)}`

`= 47 [100P\ – (53 xx 147^(k – 1))] + 53 xx 147 xx 147^(k – 1)`

`= 4700P\ – 2491 xx 147^(k – 1) + 7791 xx 147^(k – 1)`

`= 4700P + 5300 xx 147^(k – 1)`

`= 100 (47P + 53 xx 147^(k – 1))`

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

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

Proof, EXT1 P1 2012 HSC 12a

Use mathematical induction to prove that `2^(3n)\ – 3^n` is divisible by `5` for `n >= 1`. (3 marks)

--- 14 WORK AREA LINES (style=lined) ---

Show Answers Only

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

Show Worked Solution

`text(Prove by induction)`

`2^(3n)\ – 3^n\ text(is divisible by)\ 5\ text(for)\ n >= 1`

`text(If)\ n = 1`

`2^(3n)\ – 3^n`	`= 2^3\ – 3^1`
	`= 5\ \ \ \ text{(divisible by 5)}`

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

IMPORTANT: Making `3^k` or `2^(3k)` the subject helps for the substitution required in the proof for `n+1`. Important to state that `P` is an integer.

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

`text(i.e.)\ \ 2^(3k)\ – 3^k`	`= 5P\ \ \ \ text{(} P\ text{integer)}`
`3^k`	`= 2^(3k)\ – 5P\ \ …\ text{(1)}`

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

`2^(3(k+1))\ – 3^(k+1)`	`= 2^(3k + 3)\ – 3 * 3^k`
	`= 2^3 * 2^(3k)\ – 3(2^(3k)\ – 5P)\ \ \ text{(from (1) above)}`
	`= 8 * 2^(3k)\ – 3 * 2 ^(3k) + 15P`
	`= 5 * 2^(3k) + 15P`
	`= 5 (2^(3k) + 3P)`

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

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

`47^1 + 53 xx 147^(1 – 1)`	`= 47 + 53`
	`= 100\ \ text{(divisible by 100)}`