Using mathematical induction, show
`sum_(r=1)^n r^2=(n(n+1)(2n+1))/6` for `n>=1.` (3 marks)
--- 9 WORK AREA LINES (style=lined) ---
Aussie Maths & Science Teachers: Save your time with SmarterEd
Using mathematical induction, show
`sum_(r=1)^n r^2=(n(n+1)(2n+1))/6` for `n>=1.` (3 marks)
--- 9 WORK AREA LINES (style=lined) ---
`text{Proof (See Worked Solution)}`
`text{Prove true for}\ \ n=1:`
`text{LHS}\ =sum_(r=1)^1 n^2=1^2=1`
`text{RHS}\ =(1xx2xx3)/6=1=\ text{LHS}`
`:.\ text{True for}\ \ n=1`
`text{Assume true for}\ \ n=k:`
`sum_(r=1)^k r^2=(k(k+1)(2k+1))/6`
`text{Prove true for}\ \ n=k+1:`
`text{i.e.}\ sum_(r=1)^(k+1) r^2=((k+1)(k+2)(2k+3))/6`
`sum_(r=1)^(k+1) r^2` | `=sum_(r=1)^k r^2+(k+1)^2` | |
`=(k(k+1)(2k+1))/6+(k+1)^2` | ||
`=((k+1)[2k^2+k+6k+6])/6` | ||
`=((k+1)(2k^2+7k+6))/6` | ||
`=((k+1)(k+2)(2k+3))/6` | ||
`=\ text{RHS}` |
`:.\ text{True for}\ \ n=k+1`
`:.\ text{Since true for} \ n=1,\ text{by PMI, true for integers} \ n>=1.`
Using mathematical induction, show
`1/4n^4<sum_(r=1)^n r^3<=n^4` for `n>=1.` (4 marks)
`text{Proof (See Worked Solution)}`
`text{Prove true for}\ \ n=1:`
`text{LHS}\ =1/4`
`text{Middle}\ =1^3=1`
`text{RHS}\ =1^4=1`
`1/4<1<=1`
`:.\ text{True for}\ \ n=1`
`text{Assume true for}\ \ n=k:`
`text{i.e.}\ 1/4k^4<sum_(r=1)^k r^3<=k^4`
`text{Prove true for}\ \ n=k+1:`
`text{i.e.}\ 1/4(k+1)^4<sum_(r=1)^(k+1) r^3<=(k+1)^4`
`text{LHS}\ =1/4(k+1)^4=1/4(k^4+4k^3+6k^2+4k+1)`
`text{RHS}\ =k^4+4k^3+6k^2+4k+1`
`text{Middle}\ =sum_(r=1)^(k+1) r^3=sum_(r=1)^k r^3+(k+1)^3`
`text{Consider LHS to show}\ \ 1/4(k+1)^4<sum_(r=1)^(k+1) r^3`
`text{Middle}` | `=sum_(r=1)^k r^3+(k+1)^3` | |
`>1/4k^4+(k^3+3k^2+3k+1)` | ||
`>1/4(k^4+4k^3+12k^2+12k+4)` | ||
`>1/4(k^4+4k^3+6k^2+4k+1), \ \ (k>=1)` | ||
`>\ text{LHS}` |
`text{Consider RHS to show}\ \ sum_(r=1)^(k+1) r^3<=k^4`
`text{Middle}` | `=sum_(r=1)^k r^3+(k+1)^3` | |
`<=k^4+k^3+3k^2+3k+1` | ||
`<=k^4+4k^3+6k^2+4k+4,\ \ (k>=1 => 4k^3>k^3, 6k^2>3k^2, 4k>3k)` | ||
`<=(k+1)^4` | ||
`<=\ text{RHS}` |
`:.\ text{True for}\ \ n=k+1`
`:.\ text{Since true for} \ n=1,\ text{by PMI, true for integers} \ n>=1.`
Let `J_(n)=int_(0)^(1)x^(n)e^(-x)\ dx`, where "n" is a non-negative integer.
--- 2 WORK AREA LINES (style=lined) ---
--- 3 WORK AREA LINES (style=lined) ---
--- 4 WORK AREA LINES (style=lined) ---
--- 6 WORK AREA LINES (style=lined) ---
--- 5 WORK AREA LINES (style=lined) ---
i. | `J_0` | `=int_0^1 e^(-x)\ dx` |
`=[-e^(-x)]_0^1` | ||
`=-e^(-1)+1` | ||
`=1-1/e` |
ii. `text{Show}\ \ J_n<=1/(n+1)`
`text{Note:}\ e^(-x)<1\ \ text{for}\ \ x in [0,1]`
`J_n` | `=int_0^1 x^n e^(-x)\ dx` | |
`leq int_0^1 x^n \ dx` | ||
`leq 1/(n+1)[x^(n+1)]_0^1` | ||
`leq 1/(n+1)(1^(n+1)-0)` | ||
`leq 1/(n+1)\ \ text{… as required}` |
iii. `text{Show}\ \ J_n=nJ_(n-1)-1/e`
`u` | `=x^n` | `v′` | `=e^(-x)` |
`u′` | `=nx^(n-1)` | `v` | `=-e^(-x)` |
`J_n` | `=[-x^n * e^(-x)]_0^1-int_0^1 nx^(n-1)*-e^(-x)\ dx` | |
`=(-1^n * e^(-1)+0^n e^0)+nint_0^1 x^(n-1)*e^(-x)\ dx` | ||
`=nJ_(n-1)-1/e` |
iv. `text{Prove}\ \ J_(n)=n!-(n!)/(e)sum_(r=0)^(n)(1)/(r!)\ \ text{for}\ \ n >= 0`
`text{If}\ \ n=0:`
`text{LHS} = 1-1/e\ \ text{(see part (i))}`
`text{RHS} = 0!-0!/e (1/(0!)) = 1-1/e(1)=\ text{LHS}`
`:.\ text{True for}\ \ n=0.`
`text{Assume true for}\ \ n=k:`
`J_(k)=k!-(k!)/(e)sum_(r=0)^(k)(1)/(r!)`
`text{Prove true for}\ \ n=k+1:`
`text{i.e.}\ \ J_(k+1)=(k+1)!-((k+1!))/(e)sum_(r=0)^(k+1)(1)/(r!)`
`J_(k+1)` | `=(k+1)J_k-1/e\ \ text{(using part (iii))}` | |
`=(k+1)(k!-(k!)/(e)sum_(r=0)^(k)(1)/(r!))-1/e` | ||
`=(k+1)!-((k+1)!)/(e)sum_(r=0)^(k)(1)/(r!)-1/e xx ((k+1)!)/((k+1)!)` | ||
`=(k+1)!-((k+1)!)/e(\ sum_(\ r=0)^(k)(1)/(r!)+1/((k+1)!))` | ||
`=(k+1)!-((k+1)!)/e(\ sum_(\ r=0)^(k+1)(1)/(r!))` |
`=>\ text{True for}\ \ n=k+1`
`:.\ text{S}text{ince true for}\ n=1,\ text{by PMI, true for integers}\ n>=1`
v. `0<=J_n<= 1/(n+1)\ \ \ text{(part (ii))}`
`lim_(n->oo) 1/(n+1)=0\ \ => \ lim_(n->oo) J_n=0`
`text{Using part (iv):}`
`J_n/(n!)` | `=1-1/e sum_(r=0)^(n)(1)/(r!)` | |
`1/e sum_(r=0)^(n)(1)/(r!)` | `=1-J_n/(n!)` | |
`sum_(r=0)^(n)(1)/(r!)` | `=e-(eJ_n)/(n!)` | |
`lim_(n->oo)(\ sum_(\ r=0)^(n)(1)/(r!))` | `=lim_(n->oo)(e-(eJ_n)/(n!))` | |
`=e-0` | ||
`=e` |
--- 6 WORK AREA LINES (style=lined) ---
`sum_(r = 1)^n\ text(cosec)(2^r x) = cot x - cot(2^n x)`. (2 marks)
--- 8 WORK AREA LINES (style=lined) ---
i. `text(Show)\ \ cot x – cot 2x = text(cosec)\ 2x`
`text(LHS)` | `= (cos x)/(sin x) – 1/(tan 2x)` |
`= (cos x)/(sin x) – (1 – tan^2 x)/(2 tan x)` | |
`= (cos x)/(sin x) – ((1 – (sin^2 x)/(cos^2 x))/(2 (sin x)/(cos x)))` | |
`= (cos x)/(sin x) – ((cos^2 x – sin^2 x)/(2 sin x cos x))` | |
`= (2 cos^2 x – cos^2 x + sin^2 x)/(2 sin x cos x)` | |
`= 1/(sin 2x)` | |
`= text(cosec)\ 2x` | |
`= text(RHS)` |
ii. `text(Prove)\ \ sum_(r = 1)^n\ text(cosec)(2^rx) = cot x – cot 2^n x\ \ text(for)\ \ n >= 1`
`text(Show true for)\ \ n = 1:`
`text(LHS) = text(cosec)(2x)`
`text(RHS) = cot x – cot 2x = text(cosec)(2x)\ \ text{(using part (i))}`
`:.\ text(True for)\ \ n = 1`
`text(Assume true for)\ \ n = k:`
`text(cosec)\ 2x + text(cosec)\ 4x + … + text(cosec)\ 2^rx = cot x – cot 2^r x`
`text(Prove true for)\ \ n = k + 1:`
`text(i.e. cosec)\ 2x + … + text(cosec)\ 2^r x + text(cosec)\ 2^(r + 1) x = cot x – cot 2^(r + 1) x`
`text(LHS)` | `= cot x – cot 2^r x + text(cosec)\ 2^(r + 1) x` |
`= cot x – cot 2^r x + text(cosec)\ (2.2^r x)` | |
`= cot x – cot 2^r x + cot 2^r x – cot 2^(r + 1) x` | |
`= cot x – cot 2^(r + 1) x` | |
`= text(RHS)` |
`:.\ text(True for)\ \ n=k+1`
`:.\ text(S)text(ince true for)\ \ n=1, text(by PMI, true for integral)\ \ n>=1.`
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.
Show that, for `n > 2`, the number of such derangements is `(n - 1) D (n - 2).` (1 mark)
--- 4 WORK AREA LINES (style=lined) ---
--- 6 WORK AREA LINES (style=lined) ---
--- 2 WORK AREA LINES (style=lined) ---
--- 5 WORK AREA LINES (style=lined) ---
--- 8 WORK AREA LINES (style=lined) ---
i. `text(Tom and one other person can have each)`
`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:)`
`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)]` |
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`
`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`
`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.`
--- 5 WORK AREA LINES (style=lined) ---
--- 8 WORK AREA LINES (style=lined) ---
--- 6 WORK AREA LINES (style=lined) ---
`qquad tan\ pi/4 + 1/2 tan\ pi/8 + 1/4 tan\ pi/16 + ….` (2 marks)
--- 4 WORK AREA LINES (style=lined) ---
i. `t=tan\ theta/2, \ \ \ sin theta=(2t)/(1+t^2),\ \ \ cos theta=(1-t^2)/(1+t^2)`
`text(Prove)\ \ cot theta + 1/2 tan\ theta/2 = 1/2 cot\ theta/2`
`text(LHS)` | `=cot theta + 1/2 tan\ theta/2` |
`=cos theta/sin theta+ 1/2 tan\ theta/2` | |
`=(1-t^2)/(2t)+t/2` | |
`=(1-t^2+t^2)/(2t)` | |
`=1/(2t)` | |
`=1/2 cot\ theta/2` | |
`=\ text(RHS)` |
ii. `text(If)\ \ n = 1`
`text(LHS)` | `=1/2^0 tan\ x/2^1=tan\ x/2` |
`text(RHS)` | `=1/2^0 cot\ x/2 – 2 cot x` |
`=cot\ x/2 – 2 cot x` |
`text{Using part (i)},\ \ 1/2 tan\ theta/2` | `= 1/2 cot\ theta/2 – cot theta,` |
`:.tan\ theta/2` | `= cot\ theta/2 – 2 cot theta` |
`text(RHS)` | `=tan\ x/2` |
`=\ text(LHS)` | |
`:.\ text(True for)\ \ n=1` |
`text(Assume true for)\ \ n = k`
`text(i.e.)\ \ sum_(r = 1)^k 1/2^(r – 1) tan\ x/2^r = 1/2^(k – 1) cot\ x/2^k – 2 cot x.`
`text(Prove the result true for)\ \ n = k+1`
`text(i.e.)\ \sum_(r = 1)^(k + 1) 1/2^(r – 1) tan x/2^r = 1/2^k cot x/2^(k + 1) – 2 cot x`
`text(LHS)` | `=sum_(r = 1)^(k) 1/2^(r – 1) tan x/2^r + 1/2^k tan x/2^(k + 1)` |
`=1/2^(k – 1) cot x/2^k – 2 cot x + 1/2^k tan x/2^(k + 1)` | |
`=1/2^(k – 1) (cot x/2^k + 1/2 tan x/2^(k +1)) – 2 cot x,\ \ \ \ text{(Let}\ \ theta=x/2^ktext{)}` | |
`=1/2^(k – 1)(cot\ theta + 1/2 tan\ theta/2) – 2 cot x` | |
`=1/2^(k – 1)(1/2 cot\ theta/2) – 2 cot x,\ \ \ \ text{(from part (i))}` | |
`=1/2^k cot\ theta/2 – 2 cot x` | |
`=1/2^k cot x/2^(k + 1) – 2 cot x` | |
`=\ text(RHS)` |
`=>text(True for)\ \ n = k + 1\ \ text(if it is true for)\ \ n = k.`
`:.text(S)text(ince true for)\ \ n = 1,\ text(by PMI, true for integral)\ \ n >= 1.`
iii. `lim_(n -> oo) sum_(r = 1)^n 1/2^(r – 1) tan x/2^r `
`=lim_(n -> oo) (1/2^(n-1) cot x/2^n – 2 cot x)`
`=lim_(n -> oo) (2/x * x/2^n * 1/(tan x/2^n) – 2 cot x)`
`=2/x xx lim_(n -> oo) ((x/2^n)/(tan x/2^n)) – 2 cot x`
`=>text(As)\ \ n -> oo,\ \ x/2^n=theta->0, and`
`=>lim_(theta-> 0) (theta)/(tan theta) =1`
`:.lim_(n -> oo) sum_(r = 1)^n 1/2^(r – 1) tan x/2^r =2/x – 2 cot x`
iv. `tan\ pi/4 + 1/2 tan\ pi/8 + 1/4 tan\ pi/16 + …`
`=lim_(n -> oo) sum_(r = 1)^n 1/2^(r – 1) tan (pi/2)/2^r`
`=(2/(pi/2)) – 2 cot pi/2`
`=4/pi`
--- 3 WORK AREA LINES (style=lined) ---
--- 10 WORK AREA LINES (style=lined) ---
--- 3 WORK AREA LINES (style=lined) ---
i. `text(Let)\ \ A=tan^(-1)\ x, and B=tan^(-1)y`
`=> tan\ A=x, and tan\ B=y`
`tan\ (A+B)` | `=(tan A + tan B)/(1-tanAtanB)` |
`=(x+y)/(1-xy)` | |
`:. A+B` | `= tan^(-1)\ ((x+y)/(1-xy))\ \ \ text(… as required)` |
ii. `sum_(j = 1)^n\ tan^(-1)\ (1/(2j^2)) = tan^(-1)\ (n/(n + 1))`
`text(If)\ \ j=1`
`text(LHS)` | `=tan^(-1)\ (1/2)` |
`text(RHS)` | `=tan^(-1)\ (1/(1 + 1))` |
`=tan^(-1)\ (1/2)` | |
`=\ text(LHS)` |
`=>\ text(True for)\ \ j = 1.`
`text(Assume true)`
`sum_(j = 1)^n\ tan^(-1)\ (1/(2j^2)) = tan^(-1)\ (n/(n + 1))`
`text(Need to prove)`
`sum_(j = 1)^(n + 1)\ tan^(-1)\ (1/(2j^2)) = tan^(-1)\ ((n + 1)/(n + 2))`
`text(LHS)` | `=sum_(j = 1)^(n + 1)\ tan^(-1)\ (1/(2j^2))` |
`=tan^(-1)\ (n/(n + 1)) + tan^(-1)\ (1/(2(n + 1)^2))` | |
`=tan^(-1)\ ((n/(n + 1) + 1/(2(n + 1)^2))/(1 − n/(n + 1) xx 1/(2(n + 1)^2))),\ \ \ text{(using part (i))}` | |
`=tan^(-1)\ ((2n(n + 1)^2 + n + 1)/(2(n + 1)^3 − n))` | |
`=tan^(-1)\ (((n + 1)(2n^2 + 2n + 1))/(2(n + 1)^3 − n))` | |
`=tan^(-1)\ (((n + 1)(2n^2 + 2n + 1))/(2n^3 + 6n^2 + 6n + 2 − n))` | |
`=tan^(-1)\ (((n + 1)(2n^2 + 2n + 1))/(2n^3 + 6n^2 + 5n + 2))` | |
`=tan^(-1)\ (((n + 1)(2n^2 + 2n + 1))/((n + 2)(2n^2 + 2n + 1)))` | |
`=tan^(-1)\ ((n + 1)/(n + 2))` | |
`=\ text(RHS)` |
`=> text(True for)\ \ j=n+1`
`:.text(S)text(ince true for)\ \ j = 1,\ text(by PMI, true for integral)\ \ j>=1`
iii. | `lim_(n → ∞) sum_(j = 1)^n\ tan^(-1)\ (1/(2j^2))` | `= lim_(n → ∞)\ tan^(-1)\ (n/(n + 1))` |
`= lim_(n → ∞)\ tan^(-1)\ (1/(1 + 1/n))` | ||
`= tan^(-1)\ 1` | ||
` = pi/4` |
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)
--- 10 WORK AREA LINES (style=lined) ---
`text(Proof)\ \ text{(See Worked Solutions)}`
`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`