PMI Series Problems – 1

Skill Builder Questions

Principles of Mathematical Induction – Series Problems

Click here to Download Question Paper

Question 1:

Prove by induction that \(1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{1}{6}n(n+1)(2n+1)\)

\(1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{1}{6}n(n+1)(2n+1)\)

Base Case

For \(n=1\): \(LHS = 1^2 = 1\)

\(RHS = \frac{1}{6}(1)(1+1)(2(1)+1) = \frac{1}{6}(1)(2)(3) = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n=k\):

\(1^2 + 2^2 + \dots + k^2 = \frac{1}{6}k(k+1)(2k+1)\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1^2 + 2^2 + \dots + k^2 + (k+1)^2\)

Using the induction hypothesis:

\(\quad = \frac{1}{6}k(k+1)(2k+1) + (k+1)^2\)

Factor \((k+1)\):

\(\quad = (k+1)\left[ \frac{k(2k+1)}{6} + (k+1) \right]\)

Simplify the bracket:

\(\quad = (k+1)\left[ \frac{2k^2 + k}{6} + \frac{6k + 6}{6} \right]\)
\(\quad = (k+1)\left[ \frac{2k^2 + k + 6k + 6}{6} \right]\)
\(\quad = (k+1)\left[ \frac{2k^2 + 7k + 6}{6} \right]\)

Factor the quadratic \(2k^2 + 7k + 6 = (2k+3)(k+2)\):

\(\quad = \frac{(k+1)(k+2)(2k+3)}{6}\)

This matches the formula for \(n = k+1\):

\(\frac{1}{6}(k+1)\big[(k+1)+1\big]\big[2(k+1)+1\big]\)

Hence, by the principles of mathematical induction,

\({1^2 + 2^2 + \dots + n^2 = \frac{1}{6}n(n+1)(2n+1)}\) holds for all \(n \in \mathbb{Z}^+\).

Question 2:

Prove by induction that \(1 + 4 + 7 + \dots + (3n – 2) = \frac{1}{2}n(3n – 1)\)

Base Case

For \(n=1\): \(LHS = 1\)

\(RHS = \frac{1}{2}(1)(3(1) – 1) = \frac{1}{2}(1)(2) = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n = k\):

\(1 + 4 + 7 + \dots + (3k – 2) = \frac{1}{2}k(3k – 1)\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1 + 4 + 7 + \dots + (3k – 2) + (3(k+1) – 2)\)

Using the induction hypothesis:

\(\quad = \frac{1}{2}k(3k – 1) + (3k + 1)\)

Write \(3k + 1\) as \(\frac{6k + 2}{2}\):

\(\quad = \frac{1}{2}k(3k – 1) + \frac{6k + 2}{2}\)

Combine over a common denominator:

\(\quad = \frac{3k^2 – k + 6k + 2}{2}\)

\(\quad = \frac{3k^2 + 5k + 2}{2}\)

Factor the numerator:

\(3k^2 + 5k + 2 = (3k + 2)(k + 1)\)

Thus: \(\quad = \frac{(k+1)(3k + 2)}{2}\)

This matches the formula for \(n = k+1\):

\(\frac{1}{2}(k+1)\big[3(k+1) – 1\big]\)

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\).

Question 3:

Prove by induction that \(1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n – 1\)

Solution

\(1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n – 1\)

Base Case

For \(n=1\): \(LHS = 1\)

\(RHS = 2^1 – 1 = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n = k\):

\(1 + 2 + 4 + \dots + 2^{k-1} = 2^k – 1\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1 + 2 + 4 + \dots + 2^{k-1} + 2^k\)

Using the induction hypothesis:

\(\quad = (2^k – 1) + 2^k\)

Simplify:

\(\quad = 2^k + 2^k – 1\)

\(\quad = 2 \cdot 2^k – 1\)

\(\quad = 2^{k+1} – 1\)

This matches the formula for \(n = k+1\).

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\).

Question 4:

Prove by induction that \(1^2 + 3^2 + 5^2 + \dots + (2n – 1)^2 = \frac{1}{3}n(4n^2 – 1)\)

\(1^2 + 3^2 + 5^2 + \dots + (2n – 1)^2 = \frac{1}{3}n(4n^2 – 1)\)

Base Case

For \(n=1\):

\(LHS = 1^2 = 1\)

\(RHS = \frac{1}{3}(1)\big[4(1)^2 – 1\big] = \frac{1}{3}(1)(3) = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n = k\):

\(1^2 + 3^2 + 5^2 + \dots + (2k – 1)^2 = \frac{1}{3}k(4k^2 – 1)\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1^2 + 3^2 + 5^2 + \dots + (2k – 1)^2 + \big[2(k+1) – 1\big]^2\)

Using the induction hypothesis:

\(\quad = \frac{1}{3}k(4k^2 – 1) + (2k + 1)^2\)

Expand \((2k + 1)^2\):

\(\quad = \frac{1}{3}k(4k^2 – 1) + 4k^2 + 4k + 1\)

Write the second term with denominator 3:

\(\quad = \frac{1}{3}k(4k^2 – 1) + \frac{12k^2 + 12k + 3}{3}\)

Combine over a common denominator:

\(\quad = \frac{4k^3 – k + 12k^2 + 12k + 3}{3}\)

Simplify: \(\quad = \frac{4k^3 + 12k^2 + 11k + 3}{3}\)

Factor the cubic:\(4k^3 + 12k^2 + 11k + 3 = (k+1)(4k^2 + 8k + 3)\)

Thus: \(\quad = \frac{(k+1)(4k^2 + 8k + 3)}{3}\)

Notice that \(4k^2 + 8k + 3 = 4(k+1)^2 – 1\):

\(\quad = \frac{(k+1)\big[4(k+1)^2 – 1\big]}{3}\)

This matches the formula for \(n = k+1\).

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\).

Question 5:

Prove by induction that \(1^2 – 2^2 + 3^2 – \dots + (-1)^{n-1}n^2 = \frac{1}{2}(-1)^{n-1}n(n+1)\)

\(1^2 – 2^2 + 3^2 – \dots + (-1)^{n-1}n^2 = \frac{1}{2}(-1)^{n-1}n(n+1)\)

Base Case

For \(n=1\):

\(LHS = 1^2 = 1\)

\(RHS = \frac{1}{2}(-1)^{1-1}(1)(1+1) = \frac{1}{2}(1)(2) = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n = k\):

\(1^2 – 2^2 + 3^2 – \dots + (-1)^{k-1}k^2 = \frac{1}{2}(-1)^{k-1}k(k+1)\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1^2 – 2^2 + 3^2 – \dots + (-1)^{k-1}k^2 + (-1)^k(k+1)^2\)

Using the induction hypothesis:

\(\quad = \frac{1}{2}(-1)^{k-1}k(k+1) + (-1)^k(k+1)^2\)

Factor out \((k+1)\):

\(\quad = (k+1)\left[ \frac{1}{2}(-1)^{k-1}k + (-1)^k(k+1) \right]\)

Note that \((-1)^k = -(-1)^{k-1}\):

\(\quad = (k+1)\left[ \frac{1}{2}(-1)^{k-1}k – (-1)^{k-1}(k+1) \right]\)

Simplify the bracket:

\(\quad = (k+1)(-1)^{k-1}\left[ \frac{k}{2} – (k+1) \right]\)

\(\quad = (k+1)(-1)^{k-1}\left[ \frac{k – 2k – 2}{2} \right]\)

\(\quad = (k+1)(-1)^{k-1}\left[ \frac{-k – 2}{2} \right]\)

\(\quad = \frac{1}{2}(k+1)(-1)^{k} (k+2)\)

Since \(k+2 = (k+1)+1\), this matches:

\(\frac{1}{2}(-1)^{(k+1)-1}(k+1)\big[(k+1)+1\big]\)

Thus, the statement holds for \(n = k+1\).

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\).

Question 6:

Prove by induction that. \(1 + r + r^2 + \dots + r^{n-1} = \frac{1 – r^n}{1 – r}\), where \(r \neq 1\).

Solution

\(1 + r + r^2 + \dots + r^{n-1} = \frac{1 – r^n}{1 – r}\), where \(r \neq 1\).

Base Case

For \(n=1\): \(LHS = 1\)

\(RHS = \frac{1 – r^1}{1 – r} = \frac{1 – r}{1 – r} = 1\)

Hence, true for \(n=1\).

Inductive Step

Assume the statement is true for \(n = k\):

\(1 + r + r^2 + \dots + r^{k-1} = \frac{1 – r^k}{1 – r}\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1 + r + r^2 + \dots + r^{k-1} + r^k\)

Using the induction hypothesis:

\(\quad = \frac{1 – r^k}{1 – r} + r^k\)

Write \(r^k\) as \(\frac{r^k(1 – r)}{1 – r}\):

\(\quad = \frac{1 – r^k}{1 – r} + \frac{r^k(1 – r)}{1 – r}\)

Combine over a common denominator:

\(\quad = \frac{1 – r^k + r^k – r^{k+1}}{1 – r}\)

\(\quad = \frac{1 – r^{k+1}}{1 – r}\)

This matches the formula for \(n = k+1\).

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\), \(r \neq 1\).

Question 7:

Prove by induction that. \(1 \cdot 1 + 3 \cdot 2 + 5 \cdot 4 + \dots + (2n – 1)2^{n-1} = 3 + 2^n(2n – 3)\)

\(1 \cdot 1 + 3 \cdot 2 + 5 \cdot 4 + \dots + (2n – 1)2^{n-1} = 3 + 2^n(2n – 3)\)

Base Case

For \(n=1\): \(LHS = 1 \cdot 1 = 1\)

\(RHS = 3 + 2^1(2(1) – 3) = 3 + 2(-1) = 3 – 2 = 1\)

Hence, true for \(n=1\).

Inductive Step
Assume the statement is true for \(n = k\):

\(1 \cdot 1 + 3 \cdot 2 + 5 \cdot 4 + \dots + (2k – 1)2^{k-1} = 3 + 2^k(2k – 3)\) (Induction Hypothesis)

We must show it is true for \(n = k+1\):

\(\quad 1 \cdot 1 + 3 \cdot 2 + 5 \cdot 4 + \dots + (2k – 1)2^{k-1} + (2(k+1) – 1)2^{(k+1)-1}\)

Using the induction hypothesis:

\(\quad = \left[ 3 + 2^k(2k – 3) \right] + (2k + 1)2^k\)

Factor \(2^k\) from the last two terms:

\(\quad = 3 + 2^k\big[(2k – 3) + (2k + 1)\big]\)

Simplify inside the bracket:

\(\quad = 3 + 2^k(4k – 2)\)

\(\quad = 3 + 2^k \cdot 2(2k – 1)\)

\(\quad = 3 + 2^{k+1}(2k – 1)\)

Notice that \(2k – 1 = 2(k+1) – 3\):

\(\quad = 3 + 2^{k+1}\big[2(k+1) – 3\big]\)

This matches the formula for \(n = k+1\).

Hence, by induction, the formula holds for all \(n \in \mathbb{Z}^+\).

Question 8:

Prove by induction that \(\frac{1}{1\cdot3}+\frac{1}{2\cdot4}+\cdots+\frac{1}{n(n+2)}=\frac{3}{4}-\frac{2n+3}{2(n+1)(n+2)}\).

\(\frac{1}{1\cdot3}+\frac{1}{2\cdot4}+\cdots+\frac{1}{n(n+2)}=\frac{3}{4}-\frac{2n+3}{2(n+1)(n+2)}\).

Base Case

For \(n=1\):

\(LHS=\frac{1}{1\cdot3}=\frac{1}{3}\)

\(RHS=\frac{3}{4}-\frac{2\cdot1+3}{2\cdot2\cdot3}=\frac{3}{4}-\frac{5}{12}=\frac{9-5}{12}=\frac{1}{3}\)

True for \(n=1\).

Inductive Step

Assume true for \(n=k\):

\(\sum_{i=1}^{k}\frac{1}{i(i+2)}=\frac{3}{4}-\frac{2k+3}{2(k+1)(k+2)}\).

For \(n=k+1\):

\(\sum_{i=1}^{k+1}\frac{1}{i(i+2)}=\left(\frac{3}{4}-\frac{2k+3}{2(k+1)(k+2)}\right)+\frac{1}{(k+1)(k+3)}\).

Simplify the variable part:

\(-\frac{2k+3}{2(k+1)(k+2)}+\frac{1}{(k+1)(k+3)}\)

\(\quad=\frac{-(2k+3)(k+3)+2(k+2)}{2(k+1)(k+2)(k+3)}\)

\(\quad=-\frac{(2k+5)(k+1)}{2(k+1)(k+2)(k+3)}\)

\(\quad=-\frac{2k+5}{2(k+2)(k+3)}\)

Therefore,

\(\sum_{i=1}^{k+1}\frac{1}{i(i+2)}=\frac{3}{4}-\frac{2k+5}{2(k+2)(k+3)}\),

which matches the required form with \(n=k+1\).

Hence, by induction,
\(\frac{1}{1\cdot3}+\frac{1}{2\cdot4}+\cdots+\frac{1}{n(n+2)}=\frac{3}{4}-\frac{2n+3}{2(n+1)(n+2)}\) for all \(n\in\mathbb{Z}^+\).

Question 9:

Prove by induction that. \(\displaystyle \sum_{r=1}^{n}(r+1)2^{,r-1}=n,2^{,n},; n\in\mathbb{Z}^+.\)

\(\displaystyle \sum_{r=1}^{n}(r+1)2^{,r-1}=n,2^{,n},; n\in\mathbb{Z}^+.\)

Base Case

For \(n=1\):

\(\sum_{r=1}^{1}(r+1)2^{r-1}=2\cdot 2^{0}=2\)

\(1\cdot 2^{1}=2\)

True for \(n=1\).

Inductive Step

Assume true for \(n=k\):

\(\sum_{r=1}^{k}(r+1)2^{r-1}=k\cdot 2^{k}\)

For \(n=k+1\):

\(\sum_{r=1}^{k+1}(r+1)2^{r-1}=\left(\sum_{r=1}^{k}(r+1)2^{r-1}\right)+(k+2)2^{k}\)

\(=k\cdot 2^{k}+(k+2)2^{k}\)

\(=(2k+2)2^{k}\)

\(=2(k+1)2^{k}\)

\(=(k+1)2^{k+1}\)

Thus the formula holds for \(n=k+1\).

Since it is true for \(n=1\) and \(n=k \Rightarrow n=k+1\),

\(\sum_{r=1}^{n}(r+1)2^{r-1}=n\cdot 2^{n}\) is ture for all \(n\in\mathbb{Z}^+\).

Company

Links

Support

Recommend

Become an Online Tutor - IBDP, MYP, IGCSE & A-Level

Curriculum

PMI Series Problems – 1

Leave A Reply Cancel reply

Company

Links

Support

Recommend

Become an Online Tutor - IBDP, MYP, IGCSE & A-Level

Login with your site account

Register a new account

Modal title