Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski 

Matematyka Dyskretna – ćw. 3 

Dowody indukcyjne 1 

Twierdzenie o indukcji matematycznej, 

silnia, dwumian Newtona, symbol Newtona, trójkąt Pascala 

 

Udowodnienie tezy 

     dla       (     

 

) z wykorzystaniem twierdzenia o indukcji matematycznej: 

Jeżeli: 

1.  Teza 

     jest prawdziwa dla       (     

 

); 

2.  Dla dowolnego 

      (     

 

) prawdziwa jest implikacja: 

               ; 

to teza 

     jest prawdziwa dla każdego       (     

 

). 

Silnia: 

   („n silnia”) (     ) określamy następująco: 

                             

Dodatkowo określamy: 

      . 

Zatem:

 

       

       

               

                   

                        

… 

Zauważmy na przykład, że 

           ,             i ogólnie: 

                  

Symbol Newtona: 

 

 
    

  

           

 

Dwumian Newtona: 

       

 

   

 
    

 

   

 
    

   

     

 
    

   

 

 

       

 

        

 

 

   

   

 

         

   

   

 
    

 

 

 

 

Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski 

Trójkąt Pascala: 

 

 

Zadania 1 i 2 proszę rozwiązać z wykorzystaniem dowodu indukcyjnego. 

Zad. 1. Udowodnij, że dla 

     : 

(a)   

 

 

 

            

 

 

   

 

(b)  

                    

 

   

 

(c)   

 

            

 

 

    

 

   

 

(d)  

 

      

 

 

   

 

   

 

(e)   

 

 

 

   

    

 

 

   

 

 

 

Zad. 2. Udowodnij, że dla 

     : 

(a) 

     

 

     

(b) 

    

 

     

(c) 

    

 

     

(d) 

    

 

     

(e) 

     

 

   

 

  

(f) 

     

 

          

(g) 

    

   

       

 

     

Zad. 3. Udowodnij, że: 

(a) 

    

   

      

  

 jest wielokrotnością 10 

(b) 

    

  

      

 

 jest wielokrotnością 10 

(c) 

   

   

     

 

 jest wielokrotnością 10