**Problem 1.**

Solution. The proof will be by induction on n. The base
case is n = 1. The

left-hand side of the equation becomes and
the right-hand side is

Thus the base case holds.

Now as sume that the above equation hold for n = k - 1
where k ∈N is some

constant such that k - 1≥1. Thus in,

we can replace the second summaion and get,

Thus the equation holds for some k given that it holds
k-1. By induction it follows

that the equation holds for all n ∈N.

**Problem 2.**

Solution. The proof is by induction on n. The base case is
n = 0. We prove it thus,

Now, assume that the equation is true for some k ∈N and n
= k - 1≥0.

Consider,

Where the second equality comes from applying the
induction hypothesis. Continuing,

Which is the desired result for n = k. By induction, the
equation is true for all

n∈N.

**Problem 3.** Consider the fol lowing statement . the
sum of cubes of the first n

positive integers is equal to the square of the sum of these integers. Restate
this as

a formal mathematical theorem using Prove
your theorem.

Solution. Theorem 1. For n∈N and n≥1,

Proof. The proof is by induction on n. The base case is
when n = 1,

Now assume that the theorem holds for n = k - 1 for some
k∈N, k - 1≥1.

Thus we get that,

Where the last equation comes from applying the induction
hypothesis. Now we

use the fact that to show that,

Which is the equation with n = k. Therefore, by induction,
the theorem holds.

**Problem 4.** n^5 - n is divisible by 5 for every
positive integer n.

Solution. The proof will follow by induction on the n. We
prove the base case,

n = 1, follows because n^5 - n = 1^5 - 1 = 0 is divisible by 5.

Now we assume that k^5-k is divisible by 5 for some
positive integer k. Consider,

The first term is divisible by 5 because of the induction
hypothesis and the second

term is divisible by 5 because is contains a factor of 5. Thus the sum is
divisible

by 5. This proves the induction hypothesis and completes the proof.

**Problem 5.** Find (and prove) an exact closed form
solution to f (n) mapping the

natural numbers to the reals defined by

Solution. **Claim. **

The proof is by induction on n.

**Base.** (note that there are two base cases since the recurrence uses two
previous

values f (n - 1) and f(n - 2)).

and we have f(0) = 0 by
the recursive

definition of f.

and we have f(1) = 1 by
the recursive

definition of f.

**Inductive Step.** Assume n > 1. Assume
for all j such

that 0 ≤ j < n. Let IH(j) be the statement so
we are assuming

IH(j) for 0 ≤ j < n. We need to show that

Since n > 1, we can use the recursive definition of f to
get that

f(n) = 5f(n - 1) + 6f(n - 2).

We can use IH(n-1) and IH(n-2) to rewrite f(n-1) and
f(n-2). So from the

inductive hypothesis we get.

which is what we needed to show.

Problem 6. Define the following recurrence

Show that

Solution. **Proof** by induction on n. Note that there
will need to be two base cases

for this induction proof. One (n = 0) is not sufficient because then our
inductive

step would have to cover 1, . . . , n. This presents a problem because our
recurrence

is not defined for n = 1. In general when there are two recursive references to
a

function like F , namely F(n - 1 and F(n - 2), two base cases are required for a

proof by induction.

**Base Step.** n = 0. By definition
again we have

Inductive Step. Let n≥2. Assume
This is

the inductive hypothesis. Our goal is to show that this assumption implies that

Consider the recursive definition of F.

by the inductive hypothesis. Note the inequality , and that
here we have applied the

inductive hypothesis twice-once for F(n - 1) and once for F(n - 2). Continuing

on...

Recall that we are deaing with n≥2. In this case we have
that 3n - 4≥n. Of

course, this can also be proved by induction.

as desired. By the principle of mathematical induction we
are done.