David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries
Page 7 Problem 2 Answer
Given: a + ar + ar2 + …. + arn = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)
If r ≠ 1, we have to show that for any positive integer n
We want to prove that:
a + ar + ar2 + …. + arn = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)(1)
Let S be the set of all positive integers for which Equation (1) is true.
When r = 2, a + ar + ar2 = a(r2 + r + 1)
R.H.S:
\(\frac{a\left(r^3-1\right)}{r-1}=\frac{a(r-1)\left(r^2+r+1\right)}{(r-1)}\) = a(r2 + r + 1)
From (1) and (2), r = 2 satisfies
Equation (1) ⇒ 2 ∈ S Let K ∈ S then
a + ar + …. + ark = \(\frac{a\left(r^{k+1}-1\right)}{r-1}\) + ark+1
Now for
r = k + 1, a + ar + … + ark + ark+1 = \(\frac{a\left(r^{k+1}-1\right)}{r-1}\)
= \(\frac{a}{r-1}\left[r^{k+1}-1+(r-1) r^{k+1}\right]=\frac{a}{r-1}\left[r^{k+2}-1\right]\)
Which is the R.H.S of Eq.(1) when r=k+1
Thus k+1 ∈ S then S is the set of all positive integers r ≥ 2,thus Eq.(1) is true for all r ≥ 2
We get, a + ar + ar2 + …. + arn = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)
Page 7 Problem 3 Answer
Given: an−1 = (a−1)(an-1 + an-2 + an-3 + ⋯ + a + 1)
By using the Second Principle of Finite Induction we have to establish that for all n ≥ 1
an-1 = (a-1)(an-1 + an-2 + … + a + 1)
Proof: We prove it by induction. For n = 1, the relation trivially holds. Let this hold for all numbers less or equal to k i.e.
ak−1 = (a−1)(ak-1 + ak-2 + ⋯ + a + 1)
Then
ak+1 − 1 = ak+1 − ak + ak − 1
= ak(a−1) + (a−1)(ak-1 + ak-2 + ⋯ + a + 1)
= (a−1)(ak + ak-1 + ak-2 + ⋯ + a + 1)
This shows that the relation holds for number k implies it holds for k+1. Hence by principle of finite induction, this holds for all n ≥ 1.
So, the relation holds for number k implies it holds for k + 1.
Hence by principle of finite induction, this holds for all n ≥ 1.
Page 7 Problem 4 Answer
Given:
n3 = (13 + 23 + ⋯ + n3) − (13 + 23 + ⋯ + (n−1)3).
We have to prove that the cube of any integer can be written as the difference of two squares
we use the relation that
13 + 23 + … + n3 = \(\left(\frac{n(n+1)}{2}\right)^2\)
We know that
n3 = (13 + 23 + ⋯ + n3) − (13 + 23 + ⋯ + (n−1)3)
Using the above relation, we get
n3 = \(\left(\frac{n(n+1)}{2}\right)^2-\left(\frac{(n-1) n}{2}\right)^2\)
Where the terms \(\left(\frac{n(n+1)}{2}\right) \text { and }\left(\frac{(n-1) n}{2}\right)\) are integers.
We get n3 = \(\left(\frac{n(n+1)}{2}\right)^2-\left(\frac{(n-1) n}{2}\right)^2\)
Where the terms \(\left(\frac{n(n+1)}{2}\right) \text { and }\left(\frac{(n-1) n}{2}\right)\) are integers.
Page 7 Problem 5 Answer
We need to find the values of n ≤ 7 for which n!+1 is a perfect square.
We need to find the values of n ≤ 7 for which n!+1 is a perfect square.
n:1 ⇒ n! + l = 2
n:2 ⇒ n! + 1 = 3
n:3 ⇒ n! + l = 7
n:4 ⇒ n! + 1 = 52
n:5 ⇒ n! + 1 = 112
n = 6 ⇒ n!+1 = 721
n = 7 ⇒ n!+1 = 5041 = 712
Thus for n = 4,5,7 n!+1 is a perfect square
For n = 4,5,7,n! + 1 is a perfect square.
Given - For positive integers m and n,(mn)! = m!n! and (m+n)! = m!+n!.
We will determine whether the given statement is true or false.
We will use the known facts.
False.
Because(3.2)! = 720
3!.2! = 6.2
= 12
So (3.2)! ≠ 3!.2!
(3+2)! = 5!
= 120
3! + 2! = 6 + 2
= 8
So (3+2)! ≠ 3! + 2!
The given statement is false.
Page 7 Problem 6 Answer
We have to prove that n! > n2 for every integer n ≥ 4, where as n! > n3 for every integer n ≥ 6.
We prove it via finite induction. We know 4! = 24 ≥ 16 = 42 thus it works for case n = 4. Let this true for some integer k > 4. i.e. k! > k{2}.
Then
(k+1)! = (k+1)k! > (k+1)k2 > (k+1)2
[Note* here we use k2 ≥ k+1]
This shows n! > n2 for all n ≥ 4 by induction.
For n = 6, we have 6! = 720 > 216 = 63. Let this be true for some integer k i.e. k! > k3, then
(k+1)! = (k+1)k! > (k+1)k3 > (k+1)(k+1)2 = (k+1)3
[There we use k3 >(k+1)2 for all k ≥ 3].
This shows n! > n3 for all n ≥ 6.
We get that n! > n3 for all n ≥ 6.
Page 7 Problem 8 Answer
Given: 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\)
We have to verify that for all n ≥ 1
We have to prove that:
2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\)
Let S be the set of all positive integers for which Equation (1) is true.
For n = 1, 2 = \(\frac{(2) !}{1 !}\) = 2 thus 1 ∈ S
Assume K ∈ S then
2.6.10.14….(4k-2) = \(\frac{(2 k) !}{k !}\)
Now for
r = k + 1, 2.6.10.14…(4k-2).(4k+2) = \(\frac{(2 k) !}{k !}\)2(2k+1) = \(\frac{(2 k+1) !(2)}{k !} \cdot \frac{(k+1)}{(k+1)}\) = \(\frac{(2 k+2) !}{(k+1) !}=\frac{[2(k+1)] !}{(k+1) !}\) which is R.H.S of Eq(1)
When n = k + 1, thus k + 1 ∈ S
So, 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\) is true for all n ≥ 1.
thus, 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\) is true for all n ≥ 1.
By using (a)part we have to obtain that the inequality 2n(n!)2 ≤ (2n)! for all n ≥ 1.
Proof: 2n(n!) ≤ \(\frac{(2 n) !}{n !}\)
Using part (a): 2⋅6⋅10⋅14⋯(4n−2) ≥ 2n(n!)
Let S be the set of all positve integers for which Eq.(1) is true.
For n = 1,2 ≥ 2 thus 1 ∈ S
Assume k ∈ S then 2⋅6⋅10⋅14⋯(4k−2) ≥ 2k(k!)
Now for r = k+1,2⋅6⋅10⋅14⋯(4k−2)⋅(4k+2) ≥ 2k(k!)(4k+2)
= 2k(k!)2(2k+1)=2k+1(k+1)!
Therefore, k + 1 satisfies Eq.(1), thus k+1 ∈ S
Thus, 2⋅6⋅10⋅14⋯(4n−2) ≥ 2n(n!)
We get, 2.6.10.14…(4n-2) ≥ 2n(n!) is true for all n ≥ 1.
Page 7 Problem 9 Answer
We have to Establish the Bernoulli inequality: If 1 + a > 0, then(1+a)n ≥ 1 + na for all n ≥ 1.
If 1 + a > 0, we need to prove that for each integer n ≥ 1 inequality
(1+a)n ≥ 1 + na…………(1) is correct.
Let S be the set of positive integers n for which Eq.1 holds. For n = 1 (1) is true, so that 1 belongs to the set S. We assume that inequality (1) is true for a fixed integer k, so that for this k
(1+a)k ≥ 1 + ka
and we attempt to prove the validity of the formula for k+1. Next, from hypothesis that inequality(1) is correct for k we have that
(1+a)k+1 = (1+a)k(1+a)
hypothesis
≥ (1+ka)(1+a)
= 1 + ka + a + ka2
= 1 + (k+1)a
But this says that inequality (1) holds when n = k + 1, putting the integer k+1 in S so that k+1 is in S whenever k is in S. According to the induction principle, S must be the set of all positive integers.
So, the Bernoullis’s ldentity is established.
So, the Bernoullis’s ldentity is established.
Page 7 Problem 10 Answer
Given: \(\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n}\)
To find: For all n ≥ 1,prove the following by mathematical induction
\(\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n}\)For n = 1, we have
\(\frac{1}{1^2} \leq 2-\frac{1}{1}=n\)so it holds.
Let the proposition hold for any number k, i.e. \(\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{k^2} \leq 2-\frac{1}{k}\)
Then
\(\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^2}\) = \(2-\frac{1}{k+1}\left(\frac{k+1}{k}-\frac{1}{k+1}\right)\)
= \(2-\frac{1}{k+1}\left(\frac{(k+1)^2-k}{k(k+1)}\right)\)
= \(2-\frac{1}{k+1}\left(\frac{k(k+1)+1}{k(k+1)}\right)\)
< \(2-\frac{1}{k+1}\)
This shows that the relation holds for any n ≥ 1.
This shows that the relation holds for any n ≥ 1.
Given: \(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}=2-\frac{n+2}{2^n}\)
To find: For all n ≥ 1, prove the following by mathematical induction:
\(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}=2-\frac{n+2}{2^n}\)For n = 1, we have
\(2-\frac{1+2}{2^1}=2-\frac{3}{2}=\frac{1}{2}\)So the relation holds for n = 1.
Let the relation hold for some integer k, i.e.
\(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^2}+\cdots+\frac{k}{2^k}=2-\frac{k+2}{2^k}\)then
\(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^2}+\cdots+\frac{k}{2^k}+\frac{k+1}{2^{k+1}}\) = \(2-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}}\)
= \(2-\left(\frac{2(k+2)-(k+1)}{2^{k+1}}\right)\)
= \(2-\frac{k+3}{2^{k+1}}\)
This shows the relation holds for all n ≥ 1.
This shows the relation holds for all n ≥ 1.
Page 7 Problem 11 Answer
We have to show that the expression (2n)!/2nn! is an integer for all. n ≥ 0
From problem no 8, we have
2.6.10.14….(4n-2) = \(\frac{(2 n) !}{n !}\)
factoring 2 from each term on left side, we get
2n . 1.3.5.7…(2n-1) = \(\frac{(2 n) !}{n !}\)
This gives \(\frac{(2 n) !}{n ! 2^n}\) = 1.3.5.7…(2n-1) which is an integer.
We get \(\frac{(2 n) !}{n ! 2^n}\) = 1.3.5.7…(2n-1) which is an integer.
Page 7 Problem 12 Answer
Given: Consider the function defined by
T(n) = \(\begin{cases}\frac{3 n+1}{2} & \text { for } n \text { odd } \\ \frac{n}{2} & \text { for } n \text { ever }\end{cases}\)
The 3n+1 conjecture is the claim that starting from any integer n > 1, the sequence of iterates T(n),T(T(n)),T(T(T(n))),…, eventually reaches the integer 1 and subsequently runs through the values 1 and 2 . This has been verified for all n ≤ 1016.
Confirm the conjecture in the cases n = 21 and n = 23.
If n = 1, then we get T(1) = \(\frac{1}{2}(3 \cdot 1+1)=2\) and if n = 2, we get T(2) = 2/2 = 1.
For n = 21, we get the following result.
\(\begin{array}{l|l}
\mathrm{k} & T^k(21) \\
0 & 21 \\
1 & 32 \\
2 & 16 \\
3 & 8 \\
4 & 4 \\
5 & 2
\end{array}\) For n = 23, we get following result.
\mathrm{k} & T^k( \\
0 & 23 \\
1 & 35 \\
2 & 53 \\
3 & 80 \\
4 & 40 \\
5 & 20 \\
6 & 10 \\
7 & 5 \\
8 & 8 \\
9 & 4 \\
10 & 2
\end{array}\)
We get,
For n = 21
\(\begin{array}{l|l}\mathrm{k} & T^k(21) \\
0 & 21 \\
1 & 32 \\
2 & 16 \\
3 & 8 \\
4 & 4 \\
5 & 2
\end{array}\)
for n = 23
\(\begin{array}{l|l}\mathrm{k} & T^k( \\
0 & 23 \\
1 & 35 \\
2 & 53 \\
3 & 80 \\
4 & 40 \\
5 & 20 \\
6 & 10 \\
7 & 5 \\
8 & 8 \\
9 & 4 \\
10 & 2
\end{array}\)
Page 8 Problem 13 Answer
Given: Suppose that the numbers an are defined inductively by
a1= 1, a2 = 2, a3 = 3a1=1, a2 = 2, a3 = 3, and
an = an-1 + an-2 + an-3 for all n ≥ 4.
To find: Use the Second Principle of Finite Induction to show that an < 2n for every positive integer n.
Given that a1 = 1, a2 = 2, a3 = 3 and
an = an-1 + an-2 + an-3
for all n ≥ 4. Then a{n} < 2{n}.
For base case, a{n} = 1 + 2 + 3 = 6<2{4} = 16.
Let us assume that for all numbers r < k, the inequality be true.
i.e.
aτ < 2r
for all r ≤ k. Then ak+1
= ak + ak-1 + ak-2
< 2k + 2k-1 + 2k-2
= 2k-2(1+2+4)
< 2k+1
Or,
ak+1 < 2k+1
This shows that by strong induction, a{n} < 2{n} for all n ≥ 4.
This shows that by strong induction, a{n} < 2{n} for all n ≥ 4.
Page 8 Problem 14 Answer
Given: If the numbers an are defined by a1 = 11, a2 = 21, and an = 3an-1 – 2an-2 for n ≥ 3
To prove: an = 5.2n + 1 n ≥ 1
Let a1 = 11 and a2 = 21 and an be defined by
an = 3an-1 − 2an-2
Then an = 5⋅2n+1,n ≥ 1. This is true for n = 1,2,3 since
a1 = 5⋅2 + 1 = 11
a2 = 5⋅4 + 1 = 21
a3 = 41 = 3⋅21 − 2⋅11
Let this be true for all integers r ≤ k. i.e.
ar = 5⋅2r + 1,r ≤ k
Then
ak+1 = 3ak − 2ak-1
= 3(5⋅2k+1) − 2(5⋅2k-1+1)
= 5⋅2k-1(6−2) + 3 − 2
= 5⋅2k+1+1
which shows the result hold for k+1 as well.
Therefore by strong induction, the result holds for all n ≥ 1.
Therefore by strong induction, the result holds for all n ≥ 1.
Page 10 Problem 1 Answer
We have to Derive Newton’s identity
\(\left(\begin{array}{c}n \\
k
\end{array}\right)\left(\begin{array}{c}
k \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r
\end{array}\right)\left(\begin{array}{c}
n-r \\
k-r
\end{array}\right) \quad n \geq k \geq r \geq 0\)
\(\left(\begin{array}{l}
n \\
k
\end{array}\right)\left(\begin{array}{l}
k \\
r
\end{array}\right)\) = \(\frac{n !}{(n-k) ! k !} \cdot \frac{k !}{(k-r) ! r !}\)
= \(\frac{n !}{(n-r) ! r !} \cdot \frac{(n-r) !}{(n-k) !(k-r) !}\)
= \(\left(\begin{array}{l}
n \\
r
\end{array}\right)\left(\begin{array}{l}
n-r \\
k-r
\end{array}\right)\)
We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\left(\begin{array}{l}
k \\
r
\end{array}\right)\) = \(\left(\begin{array}{l}
n \\
r
\end{array}\right)\left(\begin{array}{l}
n-r \\
k-r
\end{array}\right)\)
By the Use of part (a) we have to express \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\) in terms of it predecessor: \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\) = \(\frac{n-k+1}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right) \quad n \geq k \geq 1\)
Put r = k – 1, this gives
\(\left(\begin{array}{c}n \\
k
\end{array}\right)\left(\begin{array}{c}
k \\
k-1
\end{array}\right)=\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\left(\begin{array}{c}
n-k+1 \\
1
\end{array}\right)\)
This gives
\(\left(\begin{array}{l}
n \\
k
\end{array}\right)\)k = \(\left(\begin{array}{c}
n \\
k-1
\end{array}\right)(n-k+1)\) ⇒ \(\frac{(n-k+1)}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\)
We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\)k = \(\left(\begin{array}{c}
n \\
k-1
\end{array}\right)(n-k+1)\) ⇒ \(\frac{(n-k+1)}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\)
Page 11 Problem 2 Answer
If 2 ≤ k ≤ n-2, show that
\(\left(\begin{array}{l}
n \\
k
\end{array}\right)=\left(\begin{array}{l}
n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\) n ≥ 4
Proof: let 2 ≤ k ≤ n-2 and n ≥ 4. We want to prove:
\(\left(\begin{array}{l}n \\
k
\end{array}\right)=\left(\begin{array}{l}
n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\)
Take the right hand side:
\(\left(\begin{array}{l}n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\)
= \(\frac{(n-2) !}{(k-2) !(n-k) !}+\frac{2(n-2) !}{(k-1) !(n-k-1) !}+\frac{(n-2) !}{k !(n-k-2) !}\)
= \(\frac{k(k-1)(n-2) !}{k !(n-k) !}+\frac{2 k(n-k)(n-2) !}{k !(n-k) !}+\frac{(n-k)(n-k-1)(n-2) !}{k !(n-k) !}\)
= \(\frac{\left.(n-2) ! k^2-k+2 k n 2-2 k^2+n^2-n k-n-k_R+k^2+k\right]}{k !(n-k) !}\)
= \(\frac{(n-2) !\left[n^2-n\right]}{k !(n-k) !}=\frac{n(n-1)(n-2) !}{k !(n-k) !}\)
= \(\frac{n !}{k !(n-k) !}=\left(\begin{array}{c}
n \\
k
\end{array}\right)\)
Therefore R.H.S = L.H.S.
We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)=\left(\begin{array}{l}
n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\) n ≥ 4
Page 11 Problem 4 Answer
We have to prove the following for n ≥ 1: \(\left(\begin{array}{l}
n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if 0 ≤ r < \(\frac{1}{2}(n-1)\).
Proof: for n ≥ 1,
\(\left(\begin{array}{l}n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)
<=> \(\frac{n !}{r !(n-r) !}<\frac{n !}{(r+1) !(n-r-1) !}\), 0 ≤ r, 0 ≤ n – r – 1
<=> \(frac{(r+1) !}{r !}<\frac{(n-r) !}{(n-r-1) !}\), 0 ≤ r ≤ n-1
<=> r + 1 < n – r, 0 ≤ r ≤ n-1
<=> 0 ≤ 2r ≤ n-1
<=> 0 ≤ r ≤ \(\frac{1}{2}(n-1)\)
We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if 0 ≤ r < \(\frac{1}{2}(n-1)\).
We have to prove the following for n ≥ 1: \(\left(\begin{array}{l}
n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n-1 ≥ r > \(\frac{1}{2}(n-1)\).
For n ≥ 1,
\(\left(\begin{array}{l}n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)
<=> \(\frac{n !}{r !(n-r) !}>\frac{n !}{(r+1) !(n-r-1) !}\), r ≥ 0, n – r – 1 ≥ 0
<=> \(frac{(r+1) !}{r !}<\frac{(n-r) !}{(n-r-1) !}\), r ≥ 0, n – r – 1 ≥ 0
<=> 2r > n – 1, n – 1 ≥ r ≥ 0
<=> n – 1 ≥ r ≥ \(\frac{1}{2}(n-1)\) ≥ 0
We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n-1 ≥ r > \(\frac{1}{2}(n-1)\).
We have to prove the following for n ≥ 1:
\(\left(\begin{array}{l}
n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n is odd integer, and r = \(\frac{1}{2}(n-1)\).
for n ≥ 1,
\(\left(\begin{array}{l}n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)
<=> r + 1 = n – r, n – 1 ≥ r ≥ 0
<=> 2r = n – 1, n – 1 ≥ r ≥ 0
<=> r = \(\frac{1}{2}(n-1)\), n – 1 ≥ r ≥ 0
We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n is odd integer, and r = \(\frac{1}{2}(n-1)\).
Page 12 Problem 5 Answer
For n ≥ 2, we have to prove that
\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\) = \(\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)
First, recall Pascal’s identity
\(\left(\begin{array}{c}r \\
s
\end{array}\right)+\left(\begin{array}{c}
r \\
s-1
\end{array}\right)=\left(\begin{array}{c}
r+1 \\
s
\end{array}\right), 1 \leq s \leq r\)
Proof by mathematical induction: for
for n=2, \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)=1=\left(\begin{array}{c}
2+1 \\
3
\end{array}\right)=1\)
Thus its true for n=2. Now assume it’s true for n=k then prove it for n = k + 1. Let
\(\left(\begin{array}{l}2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
k \\
2
\end{array}\right)=\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)\)
Then
\(\left(\begin{array}{l}2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
k \\
2
\end{array}\right)+\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)\)
= \(\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)+\left(\begin{array}{c}
k+1 \\
2
\end{array}\right)\)
= \(\left(\begin{array}{c}
k+2 \\
3
\end{array}\right)\)
(from Pascal’s identity)
Thus its true for n = k + 1, therefore by mathematical induction
\(\left(\begin{array}{l}2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
n \\
2
\end{array}\right)=\left(\begin{array}{c}
n+1 \\
3
\end{array}\right) . \text { for } n \geq 2\)
We get, \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\) = \(\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)
From part (a), and the relation m2 = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m for m ≥ 2,
We have to deduce the formula 12 + 22 + 32 +….+n2 = \(\frac{n(n+1)(2 n+1)}{6}\)
First we want to prove that m2 = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m for m ≥ 2
2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m <=> \(\frac{2 m !}{2 !(m-2) !}+m\) <=> m(m-1) + m = m2
Now we want to prove that:
12 + 22+ 32 +….+n2 = \(\frac{n(n+1)(2 n+1)}{6}\)
Proof:
12 + 22 + …. + n2
= \(1+2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+2+2\left(\begin{array}{l}
3 \\
2
\end{array}\right)+3+\cdots+2\left(\begin{array}{l}
n \\
2
\end{array}\right)+n\)
= \((1+2+\cdots+n)+2\left[\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)
= \((n(n+1)] \frac{3+2 n-2}{6}\)
= \(\frac{n(n+1)}{2}+\frac{2(n+1) !}{3 !(n-2) !}\)
= \(\frac{n(n+1)}{2}+\frac{(n+1)(n)(n-1)}{3}\)
= \([n(n+1)]\left(\frac{1}{2}+\frac{n-1}{3}\right)\)
= \([n(n+1)] \frac{3+2 n-2}{6}\)
= \(\frac{n(n+1)(2 n+1)}{6}\)
We get, 12 + 22 + 32 +….+n2 = \(\frac{n(n+1)(2 n+1)}{6}\)
Here, we have to prove that 1.2 + 2.3 + …. + n(n+1) = \(\frac{n(n+1)(n+2)}{3}\)
Proof: from(b)
m2 = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m ⇒ m(m-1) = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\), m ≥ 2
∴ 1.2 + 2.3 + …. + n.(n+1)
= \(2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+2\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\cdots+2\left(\begin{array}{l}
n \\
2
\end{array}\right)\)
= \(2\left[\left(\begin{array}{c}
n+2 \\
3
\end{array}\right)\right] \text { from (a) }\)
= \(2\left[\frac{(n+2) !}{3 !(n-1) !}\right]=\frac{2(n+2)(n+1)(n)}{3 \cdot 2 \cdot 1}\)
= \(\frac{n(n+1)(n+2)}{3}\)
Thus, we proved that 1.2 + 2.3 + …. + n(n+1) = \(\frac{n(n+1)(n+2)}{3}\)
Page 12 Problem 6 Answer
Here, we have to derive the binomial identity,
\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\left(\begin{array}{l}
6 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{c}
2 n \\
2
\end{array}\right)=\frac{n(n+1)(4 n-1)}{6} \quad n \geq 2\).
It’s given that m ≥ 2, \(\left(\begin{array}{c}
2 m \\
2
\end{array}\right)=2\left(\begin{array}{c}
m \\
2
\end{array}\right)+m^2\)
We can write as,
\(\left(\begin{array}{c}2 m \\
2
\end{array}\right)=\frac{(2 m) !}{2 !(2 m-2) !}=\frac{(2 m)(2 m-1)}{2}=2 m^2-m=m^2+m^2-m=m^2+2\left(\begin{array}{c}
m \\
2
\end{array}\right) \mathrm{m} \geq 2 \text { from ex } 5 \text { (c) }\)
∴ \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\left(\begin{array}{l}
6 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{c}
2 n \\
2
\end{array}\right)\)
= \(1+\left[2^2+2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots+n^2+2\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)
= \(\left(1^2+2^2+\cdots+n^2\right)+2\left[\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)
= \(\frac{n(n+1)(2 n+1)}{6}+2\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)
= \(\frac{n(n+1)(2 n+1)}{6}+\frac{2(n+1) !}{3 \cdot 3(n-2) !}\)
= \(\frac{n(n+1)(2 n+1)}{6}+\frac{6(n+1)(n)(n-1)}{6}\)
= \(\frac{n(n+1)[2 n+1+2 n-2]}{6}\)
= \(\frac{n(n+1)(4 n-1)}{6}\)
Thus, we derive the binomial identity,
\(\left(\begin{array}{l}2 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\left(\begin{array}{l}
6 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{c}
2 n \\
2
\end{array}\right)=\frac{n(n+1)(4 n-1)}{6} \quad n \geq 2\)
Page 12 Problem 7 Answer
Here, we have to verify that
12 + 32 + 52 + …. + (2n-1)2 = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)
We solve this by mathematical induction on n.
For the case n = 1, 12 = \(\left(\begin{array}{c}
3 \\
3
\end{array}\right)\) = 1
Assume that the identity is true for some k > 1.
For some k > 1,
12 + 32 + 52 + … + (2k−1)2 = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)
Add (2k+1)2 to both sides
L.H.S 12 + 32 + 52 + … + (2k-1)2 + (2k+1)2
R.H.S = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\) + (2k+1)2
= \(\frac{(2 k+1)(2 k)(2 k-1)}{6}+(2 k+1)^2\)
= \((2 k+1)\left(\frac{(2 k)(2 k-1)}{6}+2 k+1\right)\)
= \((2 k+1)\left(\frac{4 k^2+10 k+6}{6}\right)\)
= \(\frac{(2 k+1)(2 k+2)(2 k+3)}{6}\)
= \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)
Hence, the identity is true for k+1 too. This completes the induction. Hence, the identity is true for all integers greater than or equal to 1
12 + 32 + 52 + …. + (2k+1)2 = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)
Thus, we verified that
12 + 32 + 52 + …. + (2n-1)2 = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)
Page 12 Problem 8 Answer
Here, we have to show that for n ≥ 1,
\(\left(\begin{array}{c}2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)
Expand the L.H.S according to definition,
\(\left(\begin{array}{c}2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)
In the second step, cancel each (2n−2k) from the numerator by an(n−k) from the denominator. You get n 2′s in the numerator. Then multiply each term of the denominator by a 2 and multiply 2n to balance it out,
L.H.S = \(\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(2 n) !}{n ! n !}\)
= \frac{(2 n)(2 n-1) \cdots 2 \cdot 1}{n(n-1) \cdots 1 \cdot n(n-1) \cdots 1}
= \frac{(2 n-1)(2 n-3) \cdots \cdots 3 \cdot 1}{n(n-1) \cdots 1} 2^n
= \frac{(2 n-1)(2 n-3) \cdots \cdot 3 \cdot 1}{2 n(2 n-2) \cdots 2} 2^{2 n}
= \frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots \cdots 2 n} 2^{2 n}
= R.H.S
Thus, we proved that for n ≥ 1,
\(\left(\begin{array}{c}2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)
Page 12 Problem 9 Answer
Here, we have to show that x > y > z, hence x2 > xy > xz and establish the inequality \(2^n<\left(\begin{array}{c}
2 n \\
n
\end{array}\right)<2^{2 n}\), for n > 1. It’s given that x = 2.4.6…(2n), y = 1.3.5….(2n-1), and z = 1.2.3….n
Proof : We want to prove by induction that
n! < 1⋅3⋅5⋅⋅⋅⋅⋅(2n−1) for n > 1,for n = 2,2!<1⋅3, thus it’s true for n = 2. Now assume it’s true for n = k, let k! < 1⋅3⋅5⋅⋅⋅⋅(kn−1),then
(k+1)! = k!(k+1) < 1⋅3⋅5⋅⋅⋅⋅(kn−1)(k+1) < 1⋅3⋅5⋅⋅⋅⋅⋅(2k−1)(2k+1)
Note that: 2kk! = 2.4.6….2n-1
So,
2kk! < 1.3.5….(2k-1)2k
⇒ \(1<\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2^k k !}\)
= \(\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdots 2 k !}\)
∴ \(2^k<\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k} 2^{2 k}=\left(\begin{array}{c}
2 k \\
k
\end{array}\right)\)
Now, since 2m−1 < 2m for m ≥ 1 for m ≥ 1,then 1⋅3⋅5⋯(2k−1)<2⋅4⋅6⋯2k
So, \(\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k}\), for k ≥ 1
Therefore, by ex (8),
\(\left(\begin{array}{c}2 k \\
k
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k} 2^{2 k}<2^{2 k}, n \geq 1\)
Thus, we establish the equality \(2^n<\left(\begin{array}{c}
2 n \\
n
\end{array}\right)<2^{2 n}\), for n > 1
Page 12 Problem 10 Answer
Here, we have to prove that Cn can be given inductively by Cn = \(\frac{2(2 n-1)}{n+1} C_{n-1}\). It’s given that Catalan numbers, defined by
\(C_n=\frac{1}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(2 n) !}{n !(n+1) !} \quad n=0,1,2, \ldots\) from the sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…
Multiply by 2n in the numerator and the denominator,
\(\frac{2(2 n-1)}{n+1} C_{n-1}=\frac{2(2 n-1)}{n+1} \frac{(2 n-2) !}{(n-1) !(n) !}\)= \(\frac{2(2 n-1) !}{(n+1) !(n-1) !}\)
= \(\frac{2(2 n)(2 n-1) !}{2(n+1) ! n(n-1) !}\)
= \(\frac{(2 n) !}{(n+1) ! n !}\)
= Cn
Thus, we proved that Cn can be inductively by Cn = \(\frac{2(2 n-1)}{n+1} C_{n-1}\)