SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Proof, EXT2 P2 2024 HSC 14b

Use mathematical induction to prove that  \({ }^{2 n} C_n<2^{2 n-2}\),  for all integers  \(n \geq 5\).   (3 marks)

Show Answers Only

\(\text{Prove  \({ }^{2 n} C_n<2^{2 n-2}\)  for  \(n \geqslant 5\).}\)

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

\(\text{LHS}={ }^{10} C_5=252\)

\(\text{RHS}=2^8=256>\text {LHS }\)

\(\therefore\ \text{True for}\ \ n=5\)
 

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

   \({ }^{2 k} C_k<2^{2 k-2}\ \ldots\ (1)\)

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

   \(\text{i.e. } {}^{2 k+2}C_{k+1}<2^{2 k}\)

  \(\text{LHS}\) \(=\dfrac{(2 k+2)!}{(k+1)!(k+1)!}\)
    \(=\dfrac{(2 k)!}{k!k!} \times \dfrac{(2 k+1)(2 k+2)}{(k+1)(k+1)}\)
    \(={ }^{2 k} C_k \times 2 \times \dfrac{2 k+1}{k+1}\)
    \(< 2^{k-2} \times 2 \times \dfrac{2 k+1}{k+1}\)
    \(<2^k \ \ \ \left(\text{since}\ \dfrac{2 k+1}{k+1}=2-\dfrac{1}{k+1}<2\right)\)

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

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

Show Worked Solution

\(\text{Prove  \({ }^{2 n} C_n<2^{2 n-2}\)  for  \(n \geqslant 5\).}\)

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

\(\text{LHS}={ }^{10} C_5=252\)

\(\text{RHS}=2^8=256>\text {LHS }\)

\(\therefore\ \text{True for}\ \ n=5\)
 

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

   \({ }^{2 k} C_k<2^{2 k-2}\ \ldots\ (1)\)

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

   \(\text{i.e. } {}^{2 k+2}C_{k+1}<2^{2 k}\)

  \(\text{LHS}\) \(=\dfrac{(2 k+2)!}{(k+1)!(k+1)!}\)
    \(=\dfrac{(2 k)!}{k!k!} \times \dfrac{(2 k+1)(2 k+2)}{(k+1)(k+1)}\)
    \(={ }^{2 k} C_k \times 2 \times \dfrac{2 k+1}{k+1}\)
    \(< 2^{k-2} \times 2 \times \dfrac{2 k+1}{k+1}\)
    \(<2^k \ \ \ \left(\text{since}\ \dfrac{2 k+1}{k+1}=2-\dfrac{1}{k+1}<2\right)\)

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

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

Proof, EXT2 P2 2023 HSC 13b

  1. Show that  \(k^2-2 k-3 \geq 0\)  for  \(k \geq 3\).  (1 mark)

  2. Hence, or otherwise, use mathematical induction to prove that
  3.   \(2^n \geq n^2-2\), for all integers  \(n \geq 3\).  (3 marks)

Show Answers Only

i.    \(\text{Proof (See Worked Solutions)} \)

ii.   \(\text{Proof (See Worked Solutions)} \)

Show Worked Solution

i.     \(k^2-2k-3\) \(=0\)
  \( (k-3)(k+1) \) \(=0\)

\(\text{Vertex (min) at}\ (1,-4) \)

\(\text{Quadratic is monotonically increasing for}\ \ k \geq1 \)

\(\text{At}\ \ k=3, \ k^2-2k-3=0 \)

\( \therefore\ \ k^2-2 k-3 \geq 0\ \ \text{for}\ \ k \geq 3\)
 

ii.    \(\text{Prove}\ \ 2^n \geq n^2-2 \)

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

\(\text{LHS}\ = 2^3=8 \)

\(\text{RHS}\ =3^3-2=7 \leq \text{LHS} \)

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

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

\(2^k \geq k^2-2 \ \ \ …\ (*) \)
 

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

\(\text{i.e.}\ \ 2^{k+1} \geq (k+1)^2-2 \)

\(\text{LHS}\) \(=2^{k+1} \)  
  \(=2 \cdot 2^{k} \)  
  \( \geq 2(k^2-2) \ \ \ \text{(see (*) above)} \)  
  \( \geq 2k^2-4 \)  
  \( \geq k^2 + \underbrace{k^2-2k-3}_{\geq 0\ \  \text{(see part (i))}} +2k-1 \)  
  \(\geq k^2+2k-1 \)  
  \(\geq k^2+2k+1-2 \)  
  \(\geq (k+1)^2-2 \)  

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

\(\therefore \text{Since true for}\ \ n=3,\ \text{by PMI, true for integers}\ \ n\geq3 \)

Proof, EXT2 P2 EQ-Bank 7

Using mathematical induction, show

  `1/4n^4<sum_(r=1)^n r^3<=n^4`  for  `n>=1.`   (4 marks)

Show Answers Only

`text{Proof (See Worked Solution)}`

Show 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.`

Proof, EXT2 P2 2021 HSC 12d

Prove by mathematical induction that  `sqrt{n!} > 2^n` , for integers  `n ≥ 9`.  (3 marks)

Show Answers Only

`text{See Worked Solutions}`

Show Worked Solution

`text{Prove} \ sqrt{n!} > 2^n \ text{for integers} \ n≥ 9`

`text{If} \ n = 9,`

`text(LHS) = sqrt{9!} = 602.39 …`

`text(RHS) = 2^9 = 512 < 602.39 …`

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

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

`text{i.e.} \ \ sqrt{k!} > 2^k`

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

`text{i.e.} \ \ sqrt{(k + 1)!} > 2^{k + 1}`
 

`text(LHS)` `= sqrt{(k + 1)!}`
  `= sqrt{k!} sqrt{k + 1}`
  `> 2^k * sqrt{k + 1}`
  `> 2^k * 2 \ \ \ (k ≥ 9\ => \ sqrt{k + 1} > 2)`
  `> 2^{k + 1}`
 
 
`=> \ text{True for} \ \ n = k + 1`
 
`:. \ text{S} text{ince true for} \ n = 9 , text{by PMI, true for integral} \ n ≥ 9.`

Proof, EXT2 P2 2020 HSC 14c

Prove by mathematical induction that, for  `n ≥ 2`,

`frac{1}{2^2} + frac{1}{3^2} + ... + frac{1}{n^2} < frac{n - 1}{n}`    (4 marks)

Show Answers Only

`text{See Worked Solutions}`

Show Worked Solution

`text{Prove} \ frac{1}{2^2} + frac{1}{3^2} + … + frac{1}{n^2} < frac{n – 1}{n}\ \ \ text(for)\ \ n>=2`
 

`text(If)\ \ n=2:`

`text{LHS} = frac{1}{2^2} = frac{1}{4}`

`text{RHS} = frac{2-1}{2} = frac{1}{2} > text{LHS}`
 
`therefore \ text{True for} \ \ n = 2`
 

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

`frac{1}{2^2} + frac{1}{3^2} + … + frac{1}{k^2} < frac{k – 1}{k}`
 

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

`frac{1}{2^2} + frac{1}{3^2} + … + frac{1}{k^2} + frac{1}{(k + 1)^2}< frac{k}{k+1}`
 

`text{LHS}` `= frac{k – 1}{k} + frac{1}{(k + 1}^2}`
  `= frac{(k – 1)(k + 1)^2 + k}{k (k + 1)^2}`
  `= frac{(k – 1)(k^2 + 2 k +1) + k}{k(k +1)^2}`
  `= frac{k^3 + 2k^2 + k – k^2 – 2k – 1 + k}{k(k + 1)^2}`
  `= frac{k^3 + k^2 -1}{k(k + 1)^2}`
  `= frac{k^2 (k + 1 – frac{1}{k^2})}{k(k + 1)^2}`
  `= frac{k}{k +1} xx frac{(k + 1 – frac{1}{k^2})}{k +1}`
  `< frac{k}{k +1} \ \ \ (text{since} \ frac{k + 1 – frac{1}{k^2}}{k +1} < 1 )`

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

`therefore \ text{S}text{ince true for} \ n = 2, \ text{by PMI, true integral} \ n ≥ 2.`

Proof, EXT2 P2 2011 HSC 3c

Use mathematical induction to prove that  `(2n)! >= 2^n (n!)^2`  for all positive integers  `n`.  (3 marks)

Show Answers Only

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

Show Worked Solution

`text(If)\ \ n=1,`

`text(LHS) = 2! = 2`

`text(RHS) = 2 xx (1!)^2 = 2 = text(LHS)`
 

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

  `text(i.e.)\ \ (2k)! >= 2^k (k!)^2\ \ \ …\ text{(i)}`
 

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

  `text(i.e.)\ \ (2(k +1))! >= 2^(k + 1) ((k +1)!)^2`

`text(LHS)` `= (2 (k + 1))!`
  `= (2k + 2)(2k +1) xx underbrace{(2k)!}_text{using part (i)}`
  `>= (2k + 2) (2k +1) xx 2^k (k!)^2`
  `>= 2(k + 1) (2k + 1) xx 2^k (k!)^2`
  `>=2^(k+1) (k+1)(k+1) (k!)^2,\ \ \ \ \ (2k+1)>(k+1),\ text(for)\ k>0`
  `>= 2^(k + 1) ((k + 1)!)^2`

 

`=>\ 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 2005 HSC 4d

Use the principle of mathematical induction to show that  `4^n - 1 - 7n > 0`  for all integers  `n >= 2.`  (3 marks)

Show Answers Only

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

Show Worked Solution

`text(Prove)\ \ 4^n – 1 – 7n > 0\ \ text(for)\ \ n >= 2`

`text(If)\ \ n = 2`

`text(LHS)` `= 4^2 – 1 – (7 xx 2)`
  `= 16 – 1 – 14`
  `= 1 > 0`

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

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

`text(i.e.)\ \ 4^k – 1 – 7k` `> 0`
`4^k` `> 1 + 7k`

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

`text(i.e.)\ \ 4^(k + 1) – 1 – 7 (k + 1) > 0`

`text(LHS)` `= 4 (4^k) – 1 – 7k – 7`
  `> 4 (1 + 7k) – 7k – 8`
  `> 4 + 28k – 7k -8`
  `> 21k – 4`
  `> 0\ \ \ \ (k >= 2)`

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

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

Proof, EXT2 P2 EQ-Bank 8

Prove by mathematical induction that  `2^n > n^2`  for integral  `n > 4`.  (3 marks)

Show Answers Only

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

Show Worked Solution
IMPORTANT: Inequality induction is challenging. Students need to state clearly what they need to prove and then use logic to advance their answer toward the desired result.

`text(Prove)\ \ 2^n > n^2\ \ text(for integral)\ \ n > 4`

`text(If)\ \ n = 5,`

`text(LHS)` `= 2^5 = 32`
`text(RHS)` `= 5^2 = 25 < text(LHS)`

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

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

`text(i.e.)\ \ \ 2^k > k^2`

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

`text(i.e.)\ \ \ ` `2^(k + 1)` `> (k + 1)^2`
  `2^(k + 1)` `> k^2 + 2k + 1`

 

`text(LHS)` `= 2^(k + 1)`
  `= 2*2^k`
  `> 2k^2`
  `> k^2 + k^2`
  `> k^2 + 4k\ \ text{(} text(noting)\ k^2>4k,\ k>4 text{)}`
  `> k^2 + 2k + 8\ \ text{(} text(noting)\ 4k > 2k + 8,\ k > 4 text{)}`
  `> k^2 + 2k + 1`
  `> (k + 1)^2`

 

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

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

Proof, EXT2* P2 2013 HSC 14a

  1. Show that for  `k>0,\ \ 1/(k+1)^2-1/k+1/(k+1)<0`.    (1 mark)

  2. Use mathematical induction to prove that for all integers  `n>=2`,
     
        `1/1^2+1/2^2+1/3^2+\ …\ +1/n^2<2-1/n`.   (3 marks)

Show Answer Only
  1. `text{Proof (See Worked Solutions)}`
  2. `text{Proof (See Worked Solution)}`
Show Worked Solution

i.  `text(Prove that for)\ k>0,\ \ 1/(k+1)^2-1/k+1/(k+1)<0`

♦♦ Mean mark 25%.
MARKER’S COMMENT: Student algebra was poor in creating a common denominator and justifying why the final expression is always negative proved challenging.
`text(LHS)` `=(k-(k+1)^2+k(k+1))/(k(k+1)^2)`
  `=(k-(k^2+2k+1)+k^2+k)/(k(k+1)^2)`
  `=(-1)/(k(k+1)^2)`

 
`text(S)text(ince)\ \ k>0,\ text(we know)\ \ k(k+1)^2>0`

`:.\ (-1)/(k(k+1)^2)<0\ \ text(… as required)`

 

ii.  `text(Prove)\ \ 1/1^2+1/2^2+1/3^2+\ …\ +1/n^2<2-1/n\ \ text(for integer)\ \ n>=2`

`text(If)\ \ n=2`

`text(LHS)=1/1^2+1/2^2=5/4`

`text(RHS)=2-1/2=3/2 > text(LHS)`

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

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

`text(i.e.)\ \ 1/1^2+1/2^2+\ …\ +1/k^2<2-1/k`

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

`text(i.e.)\ 1/1^2+1/2^2+\ …\ +1/k^2+1/(k+1)^2<2-1/(k+1)`

♦♦ Mean mark of 26%.
IMPORTANT: Students have to carefully examine part (i) of this question to provide the information required to prove true for `n=k+1`.
`text(LHS)` `=1/1^2+1/2^2+\ …\ +1/k^2+1/(k+1)^2`
  `<2-1/k+1/(k+1)^2`
  `< underbrace{(1/(k+1)^2-1/k+1/(k+1))}_text(<0  from part i)+2-1/(k+1)`
  `<2-1/(k+1)`

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

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