Mathematical induction has part(s) inductive hypothesis
Mathematical induction is a method for proving that a statement 
  
    
      
        P
        (
        n
        )
      
    
    {\displaystyle P(n)}
   is true for every natural number 
  
    
      
        n
      
    
    {\displaystyle n}
  , that is, that the infinitely many cases 
  
    
      
        P
        (
        0
        )
        ,
        P
        (
        1
        )
        ,
        P
        (
        2
        )
        ,
        P
        (
        3
        )
        ,
        …
      
    
    {\displaystyle P(0),P(1),P(2),P(3),\dots }
    all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:Infinite descent
The method of infinite descent is a variation of mathematical induction which was used by Pierre de Fermat. It is used to show that some statement Q(n) is false for all natural numbers n. Its traditional form consists of showing that if Q(n) is true for some natural number n, it also holds for some strictly smaller natural number m. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, thereby showing (by contradiction) that Q(n) cannot be true for any n.
The validity of this method can be verified from the usual principle of mathematical induction. Using mathematical induction on the statement P(n) defined as "Q(m) is false for all natural numbers m less than or equal to n", it follows that P(n) holds for all n, which means that Q(n) is false for every natural number n.Example of error in the induction step
The induction step must be proved for all values of n. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that all horses are of the same color:Base case: in a set of only one horse, there is only one color.
Induction step: assume as induction hypothesis that within any set of 
  
    
      
        n
      
    
    {\displaystyle n}
   horses, there is only one color. Now look at any set of 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
   horses. Number them: 
  
    
      
        1
        ,
        2
        ,
        3
        ,
        …
        ,
        n
        ,
        n
        +
        1
      
    
    {\displaystyle 1,2,3,\dotsc ,n,n+1}
  . Consider the sets 
  
    
      
        
          {
          
            1
            ,
            2
            ,
            3
            ,
            …
            ,
            n
          
          }
        
      
    
    {\textstyle \left\{1,2,3,\dotsc ,n\right\}}
   and 
  
    
      
        
          {
          
            2
            ,
            3
            ,
            4
            ,
            …
            ,
            n
            +
            1
          
          }
        
      
    
    {\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}
  . Each is a set of only 
  
    
      
        n
      
    
    {\displaystyle n}
   horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
   horses.
The base case 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
   is trivial, and the induction step is correct in all cases 
  
    
      
        n
        >
        1
      
    
    {\displaystyle n>1}
  . However, the argument used in the induction step is incorrect for 
  
    
      
        n
        +
        1
        =
        2
      
    
    {\displaystyle n+1=2}
  , because the statement that "the two sets overlap" is false for 
  
    
      
        
          {
          1
          }
        
      
    
    {\textstyle \left\{1\right\}}
   and 
  
    
      
        
          {
          2
          }
        
      
    
    {\textstyle \left\{2\right\}}
  .
contains comprises includes consists of has components