- By Theorem 1.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,
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
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
In general, the amount you would have at the end of n months would be
n. (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 have P
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
n−1. The 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
−k. Thus this
payment of P at the end of n payment periods, is worth P
−k 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
- Consider the first five rows of
What is the sixth row? Now consider that
1 = 1x + 1y ,
2 = x2 + 2xy + y2, and
3 = x3 + 3x2y + 3xy2 + y3. Give a conjecture
- 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 on the
st row and those on the nth
row, the relation being =
. This is used in the inductive
≡ 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
- The binomial theorem states
n = ∑
an−kbk. Prove the
binomial theorem by induction. Hint: You might try using the preceding
- 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
- 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
- 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 formula for
. Now give a formula for a trinomial theorem, one
n. Could you continue this way and get a multinomial