Question

Provide an example of a proof by mathematical induction. Indicate whether the proof uses weak induction or strong induction. Clearly state the inductive hypothesis. Provide a justification at each step of the proof and highlight which step makes use of the inductive hypothesis.

Answer 1

We will use induction to prove that

Base step : For n =1 ,

L.H.S = 1

R.H.S  

So the statement is true for n =1 .

Induction Hypothesis : Suppose the statement is true for n = m that is , .  

Induction step : For n = m+1 ,

, Using induction hypothesis .

[ Note that here we use induction hypothesis ].

So the statement is true for n = m+1 if we assume it is true for n= m also the statement is true for n=1 . So by induction on n the statement is true for all natural number .

Now considering this example coming back to your question .

1. Which induction I used weak or strong ?

To prove the induction step we have used the fact the statement is true for n=m Hence we have used weak induction here . If we have use the statement is true for n= m , n=m-1 , n = m-2 and so on it will be called strong induction.  

Also I have mentioned in the answer where I used induction hypothesis .

.

.

If you have doubt or need more clarification at any step please comment.