# INTRODUCTION TO THE ANALYSIS OF ALGORITHMS

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.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of April 21st you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!