Use mathematical induction to prove that `15 ^(n)+6^(2n+1)` is divisible by 7 for all integers `n >= 0`. (3 marks)
--- 8 WORK AREA LINES (style=lined) ---
Aussie Maths & Science Teachers: Save your time with SmarterEd
Use mathematical induction to prove that `15 ^(n)+6^(2n+1)` is divisible by 7 for all integers `n >= 0`. (3 marks)
--- 8 WORK AREA LINES (style=lined) ---
`text{Proof (See Worked Solutions)}`
`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)` | `=15*15^(k)+6^2*6^(2k+1)` | |
`=15*15^(k)+36(7P-15^(k))\ \ text{(see (1))}` | ||
`=15*15^(k)+36*7P-36*15^(k)` | ||
`=36*7P-21*15^(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`
Prove by mathematical induction that `8^(2n + 1) + 6^(2n − 1)` is divisible by 7, for any integer `n ≥ 1`. (3 marks)
--- 10 WORK AREA LINES (style=lined) ---
`text(See Worked Solutions)`
`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.`
Use mathematical induction to prove that `7^(2n – 1) + 5` is divisible by 12, for all integers `n ≥ 1`. (3 marks)
--- 6 WORK AREA LINES (style=lined) ---
`text{Proof (See Worked Solutions)}`
`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.`
Prove by mathematical induction that `(3n + 1)7^n - 1` is divisible by 9 for integral `n >= 1`. (3 marks)
--- 10 WORK AREA LINES (style=lined) ---
`text(Proof)\ \ text{(See Worked Solutions)}`
`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`
`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`
Use mathematical induction to prove that `2^n + (− 1) ^(n + 1)` is divisible by 3 for all integers `n >= 1`. (3 marks)
--- 8 WORK AREA LINES (style=lined) ---
`text(Proof)\ \ text{(See Worked Solutions)}`
`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.`
Prove by induction that
`47^n + 53 xx 147^(n-1)`
is divisible by `100` for all integers `n >= 1`. (3 marks)
--- 10 WORK AREA LINES (style=lined) ---
`text(Proof)\ \ text{(See Worked Solutions)}`
`text(Prove)\ \ 47^n + 53 xx 147^(n – 1)\ \ text(is divisible)`
`text(by 100 for)\ n >= 1.`
`text(If)\ n = 1`
`47^1 + 53 xx 147^(1 – 1)` | `= 47 + 53` |
`= 100\ \ text{(divisible by 100)}` |
`:.\ text(True for)\ n = 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`
Use mathematical induction to prove that `2^(3n)\ – 3^n` is divisible by `5` for `n >= 1`. (3 marks)
--- 8 WORK AREA LINES (style=lined) ---
`text(Proof)\ \ text{(See Worked Solutions)}`
`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`
`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`