SB Exercises

Exercises 2.4 Exercises

1.

Prove that

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

for

n \in 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} + \dots + k^{2} = [k (k + 1) (2 k + 1)] / 6

is true. Then

\begin{aligned} 1^{2} + 2^{2} + \dots + k^{2} + (k + 1)^{2} & = [k (k + 1) (2 k + 1)] / 6 + (k + 1)^{2} \\ = [(k + 1) ((k + 1) + 1) (2 (k + 1) + 1)] / 6, \end{aligned}

and so

S (k + 1)

is true. Thus,

S (n)

is true for all positive integers

n .

🔗

2.

Prove that

🔗

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

for

n \in N .

🔗

3.

Prove that

n! > 2^{n}

for

n \geq 4 .

🔗

Answer.

The base case,

S (4) : 4! = 24 > 16 = 2^{4}

is true. Assume

S (k) : k! > 2^{k}

is true. Then

(k + 1)! = k! (k + 1) > 2^{k} \cdot 2 = 2^{k + 1},

S (k + 1)

is true. Thus,

S (n)

is true for all positive integers

n .

🔗

4.

Prove that

🔗

x + 4 x + 7 x + \dots + (3 n - 2) x = \frac{n (3 n - 1) x}{2}

for

n \in N .

🔗

5.

Prove that

10^{n + 1} + 10^{n} + 1

is divisible by 3 for

n \in N .

🔗

6.

Prove that

4 \cdot 10^{2 n} + 9 \cdot 10^{2 n - 1} + 5

is divisible by 99 for

n \in N .

🔗

7.

Show that

🔗

\sqrt[n]{a_{1} a_{2} \dots a_{n}} \leq \frac{1}{n} \sum_{k = 1}^{n} a_{k} .

🔗

8.

Use induction to prove that

1 + 2 + 2^{2} + \dots + 2^{n} = 2^{n + 1} - 1

for

n \in N .

🔗

9.

Prove the Leibniz rule for

f^{(n)} (x),

where

f^{(n)}

is the

n

th derivative of

f;

that is, show that

🔗

(f g)^{(n)} (x) = \sum_{k = 0}^{n} (\binom{n}{k}) f^{(k)} (x) g^{(n - k)} (x) .

🔗

Hint.

Follow the proof in Example 2.1.4.

🔗

10.

Prove that

🔗

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

for

n \in N .

🔗

11.

x

is a nonnegative real number, then show that

(1 + x)^{n} - 1 \geq n x

for

n = 0, 1, 2, \dots .

🔗

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 k x

is true. Then

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

S (k + 1)

is true. Therefore,

S (n)

is true for all positive integers

n .

🔗

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}) = {\emptyset, {a}, {b}, {a, b}} .

For every positive integer

n,

show that a set with exactly

n

elements has a power set with exactly

2^{n}

elements.

🔗

13.

Prove that the two principles of mathematical induction stated in Section 2.1 are equivalent.

🔗

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 \subset N

such that

1 \in S

and

n + 1 \in S

whenever

n \in 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) = r a + s b .

🔗

14 and 39
234 and 165
1739 and 9923
471 and 562
23,771 and 19,945
$- 4357$ and 3754

🔗

16.

Let

a

and

b

be nonzero integers. If there exist integers

r

and

s

such that

a r + b s = 1,

show that

a

and

b

are relatively prime.

🔗

17. Fibonacci Numbers.

The Fibonacci numbers are

🔗

1, 1, 2, 3, 5, 8, 13, 21, \dots .

We can define them inductively by

f_{1} = 1,

f_{2} = 1,

and

f_{n + 2} = f_{n + 1} + f_{n}

for

n \in N .

🔗

Prove that $f_{n} < 2^{n} .$
Prove that $f_{n + 1} f_{n - 1} = f_{n}^{2} + (- 1)^{n},$ $n \geq 2 .$
Prove that $f_{n} = [(1 + \sqrt{5})^{n} - (1 - \sqrt{5})^{n}] / 2^{n} \sqrt{5} .$
Show that $lim_{n \to \infty} f_{n} / f_{n + 1} = (\sqrt{5} - 1) / 2 .$
Prove that $f_{n}$ and $f_{n + 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,

f_{2} = 1,

and

f_{n + 2} = f_{n + 1} + f_{n} .

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

a r + b s = 1 .

Prove that

🔗

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

🔗

19.

Let

x, y \in N

be relatively prime. If

x y

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

4 k

4 k + 1

for some nonnegative integer

k .

🔗

21.

Suppose that

a, b, r, s

are pairwise relatively prime and that

🔗

\begin{aligned} a^{2} + b^{2} & = r^{2} \\ a^{2} - b^{2} & = s^{2} . \end{aligned}

🔗

Prove that

a,

r,

and

s

are odd and

b

is even.

🔗

22.

Let

n \in N .

Use the division algorithm to prove that every integer is congruent mod

n

to precisely one of the integers

0, 1, \dots, n - 1 .

Conclude that if

r

is an integer, then there is exactly one

s

Z

such that

0 \leq 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 N : a ∣ s,

b ∣ s} .

Then

S \neq \emptyset,

since

| a b | \in S .

By the Principle of Well-Ordering,

S

contains a least element

m .

To show uniqueness, suppose that

a ∣ n

and

b ∣ n

for some

n \in N .

By the division algorithm, there exist unique integers

q

and

r

such that

n = m q + r,

where

0 \leq r < m .

Since

a

and

b

divide both

m,

and

n,

it must be the case that

a

and

b

both divide

r .

Thus,

r = 0

by the minimality of

m .

Therefore,

m ∣ n .

🔗

24.

d = gcd (a, b)

and

m = lcm (a, b),

prove that

d m = | a b | .

🔗

25.

Show that

lcm (a, b) = a b

if and only if

gcd (a, b) = 1 .

🔗

26.

Prove that

gcd (a, c) = gcd (b, c) = 1

if and only if

gcd (a b, c) = 1

for integers

a,

b,

and

c .

🔗

27.

Let

a, b, c \in Z .

Prove that if

gcd (a, b) = 1

and

a ∣ b c,

then

a ∣ c .

🔗

Hint.

Since

gcd (a, b) = 1,

there exist integers

r

and

s

such that

a r + b s = 1 .

Thus,

a c r + b c s = c .

Since

a

divides both

b c

and itself,

a

must divide

c .

🔗

28.

Let

p \geq 2 .

Prove that if

2^{p} - 1

is prime, then

p

must also be prime.

🔗

29.

Prove that there are an infinite number of primes of the form

6 n + 5 .

🔗

Hint.

Every prime must be of the form 2, 3,

6 n + 1,

6 n + 5 .

Suppose there are only finitely many primes of the form

6 k + 5 .

🔗

30.

Prove that there are an infinite number of primes of the form

4 n - 1 .

🔗

31.

Using the fact that 2 is prime, show that there do not exist integers

p

and

q

such that

p^{2} = 2 q^{2} .

Demonstrate that therefore

\sqrt{2}

cannot be a rational number.

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next