Mathematical induction

Question:

It is not a plain mathematical induction question, it is a computer science question, please check the following sample:

Use mathematical induction to prove the following:

https://www.usna.edu/Users/cs/roche/courses/cs136/tutorials/t5-big.shtml 

 

Summary:

To prove:

• Firstly, the expression sum of i²= n(n+1)(2n+1)/6 is to be proved by mathematical induction. 
• Next, the expression n(n+1)(2n+1) = O(n³), should be proved by the asymptotic notation of the big-O.

 

Explanation:

To prove, we need to know about mathematical induction and asymptotic notation.

The principles of mathematical induction are:

             If there is a given statement p(n) involving the natural number n such that,

(I) The statement is true for n=1,i.e.,p(1) is true,and

(ii) If the statement is true for n=k(where k is some positive integer), then the statement is also true for n=k+1,i.e.., the truth of p(k) implies the truth of p(k+1).

Then,p(n) is true for all natural numbers n.

 

Asymptotic notation is :

                  The best algorithm to solve a problem is by checking the efficiency of the algorithm. This is performed by computing the time complexity of the algorithm. Asymptotic notations are shorthand representations of time complexity, which is represented as the fastest possible or slowest possible or average possible.

Asymptotic notations are used to indicate the order of growth of the functions, which indicate the algorithm efficiencies are:

• Big oh notation.
•  Omega notation.
•  Theta notation.

Big oh notation is a method of representing the upper bound of the algorithm’s running time. Using this notation we can specify the longest amount of time taken by the algorithm to complete.

 

Proof for mathematical induction:

Let the given statement be p(n),

p(n):

For n=1,

which is true.

Now, assume that p(k) is true for some positive integer k,

we shall now prove that p(k+1) is also true.

Now, we have

1² + 2² + 3² + 4² + …. + k² + (k + 1)²

Thus p(k+1) is true, whenever p(k) is true. Hence, from the principle of mathematical induction, the statement p(n) is true for all natural numbers n.

 

Proof for asymptotic notation of big oh notation for above proof:

By asymptotic notation of O(f(n))

A function g(n) is in O(f(n)) if there exist constants C and N such that |g(n)|<=C|f(n)| for n>N.

Here, f(n)= n³

g(n)

 

 

|g(n)| <=C|f(n)|

| n³| <=3|n³|

C=3

Therefore,

Hence, proved.

 

Also, read Using python regular expressions, write python script