- By Theorem 2.7.9 it follows that for a < b, there exists a rational number between a and
b. Show there exists an integer k such that
for some k,m integers.
- Show there is no smallest number in
. Recall means the real numbers which
are strictly larger than 0 and smaller than 1.
- Show there is no smallest number in ℚ ∩
- Show that if S ⊆ ℝ and S is well ordered with respect to the usual order on ℝ then S
cannot be dense in ℝ.
- Prove by induction that ∑
- It is a fine thing to be able to prove a theorem by induction but it is even better
to be able to come up with a theorem to prove in the first place. Derive a
formula for ∑
k=1nk4 in the following way. Look for a formula in the form
An5 + Bn4 + Cn3 + Dn2 + En + F. Then try to find the constants A,B,C,D,E, and F
such that things work out right. In doing this, show
and so some progress can be made by matching the coefficients. When you get your
answer, prove it is valid by induction.
- Prove by induction that whenever n ≥ 2,∑
- If r≠0, show by induction that ∑
k=1nark = a
- Prove by induction that ∑
- Let a and d be real numbers. Find a formula for ∑
k=1n and then prove your
result by induction.
- Consider the geometric series, ∑
k=1nark−1. Prove by induction that if r≠1,
- This problem is a continuation of Problem 11. You put money in the bank and it
accrues interest at the rate of r per payment period. These terms need a little
explanation. If the payment period is one month, and you started with $100 then the
amount at the end of one month would equal 100 = 100 + 100
r. In this the
second term is the interest and the first is called the principal. Now you have 100
in the bank. How much will you have at the end of the second month? By analogy to
what was just done it would equal
In general, the amount you would have at the end of n months would be 100
(When a bank says they offer 6% compounded monthly, this means r, the rate per
payment period equals .06∕12.) In general, suppose you start with P and it sits in the
bank for n payment periods. Then at the end of the nth payment period, you would
n in the bank. In an ordinary annuity, you make payments, P at the end
of each payment period, the first payment at the end of the first payment
period. Thus there are n payments in all. Each accrue interest at the rate of r
per payment period. Using Problem 11, find a formula for the amount you
will have in the bank at the end of n payment periods? This is called the
future value of an ordinary annuity. Hint: The first payment sits in the bank
for n − 1 payment periods and so this payment becomes P
second sits in the bank for n − 2 payment periods so it grows to P
- Now suppose you want to buy a house by making n equal monthly payments. Typically,
n is pretty large, 360 for a thirty year loan. Clearly a payment made 10 years from
now can’t be considered as valuable to the bank as one made today. This
is because the one made today could be invested by the bank and having
accrued interest for 10 years would be far larger. So what is a payment made
at the end of k payment periods worth today assuming money is worth r
per payment period? Shouldn’t it be the amount, Q which when invested
at a rate of r per payment period would yield P at the end of k payment
periods? Thus from Problem 12 Q
k = P and so Q = P
this payment of P at the end of n payment periods, is worth P
to the bank right now. It follows the amount of the loan should equal the
sum of these “discounted payments”. That is, letting A be the amount of the
Using Problem 11, find a formula for the right side of the above formula. This is called
the present value of an ordinary annuity.
- Suppose the available interest rate is 7% per year and you want to take a loan for
$100,000 with the first monthly payment at the end of the first month. If you want to
pay off the loan in 20 years, what should the monthly payments be? Hint: The rate per
payment period is .07∕12. See the formula you got in Problem 13 and solve for
- Consider the first five rows of
What is the sixth row? Now consider that
1 = 1x + 1y ,
2 = x2 + 2xy + y2,
3 = x3 + 3x2y + 3xy2 + y3. Give a conjecture about that
- Based on Problem 15 conjecture a formula for
n and prove your conjecture by
induction. Hint: Letting the numbers of the nth row of Pascal’s triangle be denoted by
, in reading from left to right, there is a relation between the numbers
st row and those on the nth row, the relation being =
This is used in the inductive step.
≡ where 0!
≡ 1 and !
n! for all n ≥ 0. Prove that
whenever k ≥ 1 and k ≤ n, then =
. Are these numbers, the same
as those obtained in Pascal’s triangle? Prove your assertion.
- The binomial theorem states
n = ∑
an−kbk. Prove the binomial theorem
by induction. Hint: You might try using the preceding problem.
- Show that for p ∈
n−k = np.
- Using the binomial theorem prove that for all n ∈ ℕ,
Hint: Show first that =
. By the binomial theorem,
Now consider the term and note that a similar term occurs in the
binomial expansion for
n+1 except that n is replaced with n + 1 whereever
this occurs. Argue the term got bigger and then note that in the binomial expansion for
n+1, there are more terms.
- Prove by induction that for all k ≥ 4, 2k ≤ k!
- Use the Problems 21 and 20 to verify for all n ∈ ℕ,
n ≤ 3.
- Prove by induction that 1 + ∑
- I can jump off the top of the Empire State Building without suffering any ill effects.
Here is the proof by induction. If I jump from a height of one inch, I am unharmed.
Furthermore, if I am unharmed from jumping from a height of n inches, then jumping
from a height of n + 1 inches will also not harm me. This is self evident and provides the
induction step. Therefore, I can jump from a height of n inches for any n. What is the
matter with this reasoning?
- All horses are the same color. Here is the proof by induction. A single horse is
the same color as himself. Now suppose the theorem that all horses are the
same color is true for n horses and consider n + 1 horses. Remove one of the
horses and use the induction hypothesis to conclude the remaining n horses are
all the same color. Put the horse which was removed back in and take out
another horse. The remaining n horses are the same color by the induction
hypothesis. Therefore, all n + 1 horses are the same color as the n − 1 horses which
didn’t get moved. This proves the theorem. Is there something wrong with this
- Let denote the number of ways of selecting a set of
k1 things, a set of k2
things, and a set of k3 things from a set of n things such that ∑
i=13ki = n. Find a
. Now give a formula for a trinomial theorem, one which
n. Could you continue this way and get a multinomial