Mathematical induction and asymptotic notation

Question:

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

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

Use mathematical induction to prove the following:

Summary:

To prove:

• Firstly, the expression sum of i³= n²(n+1)²/4 is to be proved by mathematical induction. 
• Next, the expression n²(n+1)² /4= 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 and asymptotic notation:

To  prove mathematical induction:

Let the given statement be p(n),

p(n):

By mathematical induction,

Step 1:check if it is true for n=1.

L.H.S=1³=1

R.H.S

=1

L.H.S=R.H.S

 

Step 2:

Consider it to be true for n=k.

 

Step 3:

Prove it is true for n=k+1

L.H.S

R.H.S

L.H.S=R.H.S

Hence proved.

 

To prove asymptotic notation:

By asymptotic notation:

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

Here,

g(n)=n⁴

f(n)=

Therefore f(n)=

Hence proved.

 

Also, read Create a new Java class named Student that has the following fields.