Skip to main content

Exercises 2.4 Exercises

1.

Prove that

12+22+⋯+n2=n(n+1)(2n+1)6

for n∈N.

Answer.

The base case, \(S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2\) is true.

Assume that \(S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6\) is true. Then

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6, \end{align*}

and so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\text{.}\)

2.

Prove that

13+23+⋯+n3=n2(n+1)24

for n∈N.

3.

Prove that n!>2n for n≥4.

Answer.

The base case, \(S(4): 4! = 24 \gt 16 =2^4\) is true. Assume \(S(k): k! \gt 2^k\) is true. Then \((k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}\) so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\text{.}\)

4.

Prove that

x+4x+7x+⋯+(3n−2)x=n(3n−1)x2

for n∈N.

5.

Prove that 10n+1+10n+1 is divisible by 3 for n∈N.

6.

Prove that 4⋅102n+9⋅102n−1+5 is divisible by 99 for n∈N.

7.

Show that

a1a2⋯ann≤1n∑k=1nak.
8.

Use induction to prove that 1+2+22+⋯+2n=2n+1−1 for n∈N.

9.

Prove the Leibniz rule for f(n)(x), where f(n) is the nth derivative of f; that is, show that

(fg)(n)(x)=∑k=0n(nk)f(k)(x)g(n−k)(x).
Hint.

Follow the proof in Example 2.1.4.

10.

Prove that

12+16+⋯+1n(n+1)=nn+1

for n∈N.

11.

If x is a nonnegative real number, then show that (1+x)n−1≥nx for n=0,1,2,….

Hint.

The base case, \(S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x\) is true. Assume \(S(k): (1 + x)^k -1 \geq kx\) is true. Then

\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x, \end{align*}

so \(S(k + 1)\) is true. Therefore, \(S(n)\) is true for all positive integers \(n\text{.}\)

12. Power Sets.

Let X be a set. Define the power set of X, denoted P(X), to be the set of all subsets of X. For example,

P({a,b})={∅,{a},{b},{a,b}}.

For every positive integer n, show that a set with exactly n elements has a power set with exactly 2n elements.

14.

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if S⊂N such that 1∈S and n+1∈S whenever n∈S, then S=N.

15.

For each of the following pairs of numbers a and b, calculate gcd(a,b) and find integers r and s such that gcd(a,b)=ra+sb.

  1. 14 and 39

  2. 234 and 165

  3. 1739 and 9923

  4. 471 and 562

  5. 23,771 and 19,945

  6. −4357 and 3754

16.

Let a and b be nonzero integers. If there exist integers r and s such that ar+bs=1, show that a and b are relatively prime.

17. Fibonacci Numbers.

The Fibonacci numbers are

1,1,2,3,5,8,13,21,….

We can define them inductively by f1=1, f2=1, and fn+2=fn+1+fn for n∈N.

  1. Prove that fn<2n.

  2. Prove that fn+1fn−1=fn2+(−1)n, n≥2.

  3. Prove that fn=[(1+5)n−(1−5)n]/2n5.

  4. Show that limn→∞fn/fn+1=(5−1)/2.

  5. Prove that fn and fn+1 are relatively prime.

Hint.

For Item 2.4.17.a and Item 2.4.17.b use mathematical induction. Item 2.4.17.c Show that \(f_1 = 1\text{,}\) \(f_2 = 1\text{,}\) and \(f_{n + 2} = f_{n + 1} + f_n\text{.}\) Item 2.4.17.d Use part Item 2.4.17.c. Item 2.4.17.e Use part Item 2.4.17.b and Exercise 2.4.16.

18.

Let a and b be integers such that gcd(a,b)=1. Let r and s be integers such that ar+bs=1. Prove that

gcd(a,s)=gcd(r,b)=gcd(r,s)=1.
19.

Let x,y∈N be relatively prime. If xy is a perfect square, prove that x and y must both be perfect squares.

Hint.

Use the Fundamental Theorem of Arithmetic.

20.

Using the division algorithm, show that every perfect square is of the form 4k or 4k+1 for some nonnegative integer k.

21.

Suppose that a,b,r,s are pairwise relatively prime and that

a2+b2=r2a2−b2=s2.

Prove that a, r, and s are odd and b is even.

22.

Let n∈N. Use the division algorithm to prove that every integer is congruent mod n to precisely one of the integers 0,1,…,n−1. Conclude that if r is an integer, then there is exactly one s in Z such that 0≤s<n and [r]=[s]. Hence, the integers are indeed partitioned by congruence mod n.

23.

Define the least common multiple of two nonzero integers a and b, denoted by lcm(a,b), to be the nonnegative integer m such that both a and b divide m, and if a and b divide any other integer n, then m also divides n. Prove that any two integers a and b have a unique least common multiple.

Hint.

Let \(S = \{s \in {\mathbb N} : a \mid s\text{,}\) \(b \mid s \}\text{.}\) Then \(S \neq \emptyset\text{,}\) since \(|ab| \in S\text{.}\) By the Principle of Well-Ordering, \(S\) contains a least element \(m\text{.}\) To show uniqueness, suppose that \(a \mid n\) and \(b \mid n\) for some \(n \in {\mathbb N}\text{.}\) By the division algorithm, there exist unique integers \(q\) and \(r\) such that \(n = mq + r\text{,}\) where \(0 \leq r \lt m\text{.}\) Since \(a\) and \(b\) divide both \(m\text{,}\) and \(n\text{,}\) it must be the case that \(a\) and \(b\) both divide \(r\text{.}\) Thus, \(r = 0\) by the minimality of \(m\text{.}\) Therefore, \(m \mid n\text{.}\)

24.

If d=gcd(a,b) and m=lcm(a,b), prove that dm=|ab|.

25.

Show that lcm(a,b)=ab if and only if gcd(a,b)=1.

26.

Prove that gcd(a,c)=gcd(b,c)=1 if and only if gcd(ab,c)=1 for integers a, b, and c.

27.

Let a,b,c∈Z. Prove that if gcd(a,b)=1 and a∣bc, then a∣c.

Hint.

Since \(\gcd(a,b) = 1\text{,}\) there exist integers \(r\) and \(s\) such that \(ar + bs = 1\text{.}\) Thus, \(acr + bcs = c\text{.}\) Since \(a\) divides both \(bc\) and itself, \(a\) must divide \(c\text{.}\)

28.

Let p≥2. Prove that if 2p−1 is prime, then p must also be prime.

29.

Prove that there are an infinite number of primes of the form 6n+5.

Hint.

Every prime must be of the form 2, 3, \(6n + 1\text{,}\) or \(6n + 5\text{.}\) Suppose there are only finitely many primes of the form \(6k + 5\text{.}\)

30.

Prove that there are an infinite number of primes of the form 4n−1.

31.

Using the fact that 2 is prime, show that there do not exist integers p and q such that p2=2q2. Demonstrate that therefore 2 cannot be a rational number.