18.014 Problem Set 2 Solutions - MIT Mathematics

[Pages:6]18.014 Problem Set 2 Solutions

Sam Elder

September 30, 2015

Problem 1. Let n be an integer and let x be a real number satisfying n < x < n + 1. Prove that x is not an integer. (You may assume without proof that the sum or difference of integers is an integer.)

Solution. First, we need some information about the integers. Lemma. 1 is the smallest positive integer, i.e. every positive integer n 1.1

Proof. To show this, we must use the property that the positive integers are contained in every inductive set, and then prove that one such inductive set is {x : x 1}. Indeed, if x 1, x + 1 1 + 1 1 and 1 1, so this satisfies the two properties of an inductive set. This shows that every positive integer is at least 1, as desired.

Now we proceed with the main proof by contradiction. Suppose that x is an integer satisfying n < x < n + 1. Then x - n Z as a difference of two integers. By definition, n < x implies x - n > 0, so x - n Z+. By the lemma, this shows that x - n 1. Adding n to both sides, x n + 1, which contradicts x < n + 1. Therefore, x must not be an integer.

Problem 2 (I 3.12-4). If x is an arbitrary real number, prove that there is exactly one integer n which satisfies the inequalities n x < n + 1. This n is called the greatest integer in x and is denoted by [x]. For example, [5] = 5, [5/2] = 2, and [-8/3] = -3.

Solution. First we show that there is such an integer n, and then we show that this integer is unique. We offer two proofs of the existence claim: Lemma. There exists some integer n such that n x < n + 1.

Proof 1. Suppose for sake of contradiction that no such integer n exists. By Exercise I 3.12-2, there is an integer m such that m < x. We prove by induction that every integer n x. This is easily true by transitivity for n m, so we take m as our base case. Base Case. If n = m, m < x so the claim is satisfied. Inductive Step. Suppose that n x, and we will show that n+1 x. Indeed, otherwise we have n x < n+1, but we have assumed that no such integer n exists. Therefore, n + 1 x.

So we have shown that every integer n x. But this directly contradicts Theorem I.29. So we conclude that some such integer n x < n + 1 exists.

Proof 2. Define the set S = {m Z : m x}. Since x is an upper bound for S and S is nonempty by Exercise I 3.12-2, we can define sup S = n. As x is an upper bound for S, we must have n x.

We now wish to show that n is an integer. By Theorem I.32(a) with h = 1 > 0, there is some m S with m > n - 1. Since m S, we must have m sup S = n. If there is some m < k S, then k - m Z+ so k - m 1 by the lemma from Problem 1. Then k m + 1 > n but this contradicts the definition of

1Since positive integers aren't particularly well-covered in the textbook and weren't the focus of the lectures, students may assume the result of this lemma without proof.

1

n = sup S. So there is no such k and m is an upper bound for S. As n is the least upper bound, n m, so we conclude that n = m and n is therefore an integer.

Since n is an upper bound for S, the integer n + 1 S, which implies that x < n + 1, and we have n x < n + 1 as desired.

Finally, we show uniqueness. Suppose m and n are two distinct integers satisfying m x < m + 1 and n x < n + 1. If m > n, we also have m x < n + 1 so n < m < n + 1. But this contradicts problem 1 above. Similarly, if n < m, we have m < n < m + 1, another contradiction. So there cannot be two distinct integers satisfying this pair of inequalities, as desired.

Problem 3 (I 4.10-4). Use induction to prove the binomial theorem

n

(a + b)n =

n akbn-k.

k

k=0

Then use the theorem to derive the formulas

n

n

= 2n and

n

(-1)k

n

= 0.

k

k

k=0

k=0

(Binomial coefficients are defined at the beginning of section 4.10. You can use Exercise I 4.10-3.)

Solution. As the problem suggests, we induct on n.

Base Case. We could take n = 0 as a base case, where the formula collapses to (a + b)0 = 1 =

0 0

a0b0,

but

we will also show n = 1 for clarity. When n = 1,

1 0

=

1! 1!0!

=

1 1?1

=

1

and

1 1

=

1! 0!1!

=

1 1?1

=

1

so

1 1 akb1-k = 1 a0b1 + 1 a1b0 = b + a = (a + b)1,

k

0

1

k=0

as desired.

Inductive Step. Assume that

n

(a + b)n =

n akbn-k,

k

k=0

and we will show this formula for n + 1.2 We start with the right hand side, and apply Exercise I 4.10-3:

n+1

n+1

n+1

akbn+1-k =

k

k=0

k=0

n

n

+

k-1

k

ak bn+1-k

n+1

=a

n

n+1

ak-1bn-(k-1) + b

n

ak bn-k .

k-1

k

k=0

k=0

Since

n -1

=

n n+1

= 0, we can ignore the first term of the first sum and the last term of the second sum.

Then we can reparameterize the first sum by replacing k - 1 with k. The sum will now go from 1 - 1 = 0

to (n + 1) - 1 = n. We then use the induction hypothesis:

n+1 n + 1 akbn+1-k = a n n akbn-k + b n n akbn-k = a(a + b)n + b(a + b)n = (a + b)n+1.

k

k

k

k=0

k=0

k=0

2For clarity and to match the notation of Exercise I 4.10-3, I won't be writing the formula for n = m and showing it for n = m + 1, but this is also valid and perhaps more preferable.

2

Having proved the statement for n + 1 from the statement for n, induction is complete. Finally, we verify those formulas. By taking x = a = 1, we get

n

n

n

=

n 1k1n-k = (1 + 1)n = 2n,

k

k

k=0

k=0

as desired. By taking x = -1 and a = 1, we get

n

(-1)k

n

n

=

n (-1)k1n-k = (-1 + 1)n = 0n = 0,

k

k

k=0

k=0

as desired.

Problem 4 (I 4.10-16). The numbers 1, 2, 3, 5, 8, 13, 21, . . . , in which each term after the second is the sum of its two predecessors, are called Fibonacci numbers. They may be defined by induction as follows:

a1 = 1, a2 = 2, an+1 = an + an-1 if n 2.

Prove that

n

1+ 5

an <

2

for every n 1.

Solution. As with most Fibonacci number related proofs, we proceed by induction.

Base Case. We need two base cases here: n = 1 and n = 2, as will become clear in a moment. Indeed, we have 5 > 1 as 5 > 1, so

1

1+1 1+ 5 1+ 5

a1 = 1 = 2 < 2 =

2

.

2

6+2 6+2 5 1+ 5

a2 = 2 = 4 < 4 =

2

,

as desired.

n

Inductive Step. For n 2, we assume that an <

1+ 5 2

and an-1 <

cases, we guarantee that this holds for all n 2. Then

n-1

1+ 5 2

. By taking two base

an+1 = an + an-1 <

n 1+ 5

+ 2

n-1 1+ 5

2

n-1

n-1

1+ 5

1+ 5

1+ 5

3+ 5

=

+1 =

2

2

2

2

n-1

n-1

2

n+1

1+ 5

6+2 5 1+ 5

1+ 5

1+ 5

=

=

=

,

2

4

2

2

2

as desired, completing the induction step. Induction is complete.3

3This solution is correct, but not quite written in the inductive framework that we have established. To match that framework

properly, we should instead prove by induction that for n 2, both an <

1+ 5

2

n

and an-1 <

1+ 5

2

n-1

. This redefinition

of the claim to be proved by induction also makes it clear that the base case should include bounds on both a1 and a2, but is

not required of students' solutions on this problem, as long as they include both base cases.

3

Problem 5. This exercise develops some fundamental properties of polynomials. Let f (x) =

n k=0

ck

xk

be

a polynomial of degree n. Prove each of the following statements.

Part 5.1. If n 1 and f (0) = 0, then f (x) = xg(x) where g is a polynomial of degree n - 1.

Solution. Plugging in x = 0, we have 00 = 1 and 0k = 0 if k 1, so 0 = f (0) = c0. Therefore, we can leave out this term of the sum and

n

n-1

n-1

f (x) = ckxk = ck+1xk+1 = x ck+1xk.

k=1

k=0

k=0

Define g(x) =

n-1 k=0

ck+1

xk

.

This

is

clearly

a

polynomial,

so

it

remains

to

show

it

is

degree

n - 1.

Since

f

is degree n 1, cn = 0. But cn is also the coefficient on the highest-degree term, xn-1, in g(x), so g(x) is

degree n - 1, as desired.

Part 5.2. For each real a, the function p given by p(x) = f (x + a) is a polynomial of degree n.

Solution. We induct on n to prove this statement.4

Base Case. We could use n = 0 as the base case, but for clarity will show n = 1. When n = 1, f (x) = c0+c1x, so p(x) = f (x + a) = c0 + c1(x + a) = (c0 + c1a) + c1x. This is in the form of a polynomial of degree, and since f (x) is degree 1, c1 = 0 and so p(x) is also degree 1.

Inductive Step. Suppose the statement is true for all polynomials of smaller degree than n. Define g(x) =

n-1 k=0

ck

xk

,

so

f (x)

=

g(x) + cnxn.

Now

g(x)

is

a

polynomial

of

lower

degree

so

we

can

apply

the

induction

hypothesis to it: If q(x) = g(x + a), q is also polynomial of the same degree as g, and we can write

q(x) =

n-1 k=0

dk

xk .

Therefore

p(x) = f (x + a) = g(x + a) + cn(x + a)n = q(x) + cn(x + a)n.

n

By Binomial theorem (Problem 3 on this problem set), (x + a)n =

n xkan-k. Thus we have

k

k=0

n-1

n

p(x) = dkxk + cn

n

n-1

xkan-k =

k

dk + cn

n k

an-k

xk + cnxn.

k=0

k=0

k=0

This is also the form of a polynomial, and since cn is also the leading coefficient of f (x), it is nonzero, so p(x) is also degree n, as desired.

Induction is complete.

Part 5.3. If n 1 and f (a) = 0 for some real a, then f (x) = (x - a)h(x), where h is a polynomial of degree n - 1.

Solution. Define the function p by p(x) = f (x + a), which is a polynomial of degree n by the previous part. We know p(0) = f (0+a) = f (a) = 0, so by the first part of this problem, p(x) = xq(x) for some polynomial q of degree n - 1. Then f (x) = p(x - a) = (x - a)q(x - a) = (x - a)q(x + (-a)) and by the previous part again, q(x + (-a)) is also a polynomial of degree n - 1. Letting h(x) = q(x + (-a)), we have f (x) = (x - a)h(x), as desired.

Part 5.4. If f (x) = 0 for n + 1 distinct real values of x, then every coefficient ck is zero and f (x) = 0 for all real x.

4It is not necessary to induct on n here, but it might be a little simpler. One alternative is to simply apply binomial theorem

to get p(x) = f (x + a) =

n k=0

ck (x

+

a)k

=

n k=0

ck

k l=0

k l

xl ak-l

and

then

rearrange

the

terms

of

this

sum.

4

Solution. We prove this by induction on n.

Base Case. If n = 0, then f (x) = c0 so if f (x) = 0 for 1 real value of x, c0 = 0 and f (x) = 0 for all real x, as desired.

Inductive Step. Suppose n 1 and the statement is true for all smaller values of n. Let f (x) = 0 for the

n + 1 distinct real values a1, a2, . . . , an+1. By the previous part, since f (an+1) = 0, f (x) = (x - an+1)h(x)

for some degree n - 1 polynomial h(x) =

n-1 k=0

dk xk .

We also know that 0 = f (ai) = (ai - an+1)h(ai) for any i < n + 1. Since the ai are distinct, ai - an+1 = 0,

so we conclude that h(ai) = 0 for i = 1, 2, . . . , n. This is n = (n - 1) + 1 distinct real values, so by the

induction hypothesis, all the dk are zero and h(x) = 0 for all x. But then

n-1

n-1

n-1

n-1

n-1

f (x) = (x - an+1)h(x) = dk(x - an+1)xk = dkxk+1 - dkan+1xk = 0xk+1 - 0xk = 0,

k=0

k=0

k=0

k=0

k=0

so all of the coefficients of f (x) are 0 and f (x) = 0 for all x, as desired.5

Induction is complete.

Part 5.5. Let g(x) =

m k=0

bk

xk

be a polynomial of degree m, where m n.

If g(x) = f (x) for m + 1

distinct real values of x then m = n, bk = ck for each k, and g(x) = f (x) for all real x.

Solution. We claim that h(x) = g(x) - f (x) is a polynomial of degree at most m. Indeed, we have

m

n

m

h(x) = g(x) - f (x) = bkxk - ckxk = (bk - ck)xk,

k=0

k=0

k=0

if we define ck = 0 for n < k m. Since there are no terms with xk for k > m, this is a polynomial of degree d m, as desired.

Now, if g(x) = f (x) for m + 1 distinct real values of x, then h(x) = g(x) - f (x) = 0 on these m + 1 d + 1 distinct real values. By the previous part, this implies that the coefficients of h(x) are all 0 and h(x) = 0 for all real x. Therefore bk = ck for all k as desired. Taking k = m, bm = cm, and since bm = 0, cm = 0 as well, making f (x) of degree n = m as desired. Finally, h(x) = 0 for all real x implies g(x) = f (x) for all real x, as desired.

Problem 6. In each case, find all polynomials p of degree 2 which satisfy the given conditions.

Part 6.1. p(0) = p(1) = p(2) = 1.

Answer. The only such polynomial is p(x) = 1.

Solution. Clearly p(x) = 1 satisfies these properties, so we must show that this is the only one. If q(x) = p(x) is another potential polynomial of degree d 2, q(x) = p(x) for 3 d + 1 distinct values of x (namely, 0, 1, and 2). But then by part (e) of the previous problem, p(x) and q(x) have the same coefficients, as desired.

Part 6.2. p(0) = p(1) = 1.

Answer. All solutions are of the form p(x) = 1 - ax + ax2 = 1 + ax(x - 1), where a R.

5These last couple statements might seem redundant, but in other contexts, particularly finite fields, there are polynomials which evaluate to 0 everywhere but have nonzero coefficients.

5

Solution. Indeed, if p(x) = 1 + ax(x - 1), then

p(0) = 1 + a ? 0(0 - 1) = 1 + 0 = 1 p(1) = 1 + a ? 1(1 - 1) = 1 + 0 = 1,

as desired. To show all polynomials are of this form, consider q(x) = p(x) - 1, which is also a polynomial of degree at most 2. Then q(0) = 0, so by the last problem, q(x) = xr(x) where r(x) is a polynomial of degree at most 1. Since 0 = q(1) = r(1), again by the last problem, r(x) = (x - 1)s(x) where s(x) is a polynomial of degree at most 0. But such a polynomial is just a constant, so let s(x) = a. Then

p(x) = q(x) + 1 = xr(x) + 1 = ax(x - 1) + 1 = 1 - ax + ax2,

as desired.

Problem 7. Prove that 0.999 . . . = 1.

Solution. The number 0.999 . . . is defined (c.f. section I 3.15) as the supremum of the truncated decimal

expansions:

99

9

0.999 . . . = sup 10 + 100 + ? ? ? + 10k : k 1 .

Define

xk

=

9 10

+

9 100

+???+

9 10k

.

First

we

find

a

closed-form

formula

for

these

numbers

xk :

Lemma.

xk

=1-

1 10k

.

Proof. We prove this claim by induction.

Base

Case.

If

k

= 1,

x1

=

9 10

=1-

1 10

=1-

1 10k

,

as

desired.

Inductive

Step.

Suppose

that

xk

=1-

1 10k

.

Then

99

9

99

9

9

xk+1 = 10 + 100 + ? ? ? + 10k+1 = 10 + 100 + ? ? ? + 10k + 10k+1

9

1

9

10

9

1

= xk + 10k+1 = 1 - 10k + 10k+1 = 1 - 10k+1 + 10k+1 = 1 - 10k+1 ,

as desired. Induction is complete.

Now

we

have

0.999 . . .

=

sup{1 -

1 10k

:k

1}.

Clearly

1

is

an

upper

bound

for

this

set,

as

1-

1 10k

< 1.

Suppose for sake of contradiction that there is a smaller upper bound y < 1, and we will show that there is

some xk > y. For this purpose, we use the following lemma:

Lemma. If k 1, then 10k > k.

Proof. We prove this by induction. Base Case. k = 1. Then 10k = 10 > 1 = k, as desired. Inductive Step. If 10k > k for k 1, then 10k+1 = 10 ? 10k > 2 ? 10k > 2k k + 1, as desired.

Induction is complete.

Now if y < 1, 1 - y > 0, so there is some integer k such that k(1 - y) > 1 by Theorem I.30. Therefore, by this lemma, 10k(1 - y) > 1. Solving for y, we get 1 - y > 10-k, or y < 1 - 10-k = xk, as desired. Therefore, no such y < 1 is an upper bound, making 1 the least upper bound, as desired.

6

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download