Dowody indukcyjne i funkcyjne

Zadanie 1

Udowodnij poprawność wzoru:

1 + 2 + 3 + ... + n = n(n+1)/2

Dowód indukcyjny

1. n = 1

   L = 1
   P = 1(1+1)/2 = 1
   
2. Z: 1 + 2 + 3 + ... + n = n(n+1)/2
   T: 1 + 2 + 3 + ... + n + n+1 = (n+1)(n+2)/2
   
Dowód:

   L = 1 + 2 + 3 + ... + n + n+1 = * = n(n+1)/2 + n+1 = (n(n+1) + 2(n+1))/2 = (n+1)(n+2)/2 = P
   
* korzystamy z założenia

Dowód funkcyjny

Wyznaczamy równanie rekurencyjne:

f(1) = 1
f(2) = 1 + 2 = f(1) + 2
f(3) = 1 + 2 + 3 = f(2) + 3
...
f(n) = 1 + 2 + 3 + ... + n = f(n-1) + n

Równanie rekurencyjne:

       1          ; n = 1
f(n) =
       f(n-1) + n ; n > 1

Rozwiązanie: 

f(n) = n(n+1)/2

Dowód:

1. f(1) = 1
   f(1) = 1(1+1)/2 = 1
   
2. Wykażemy, że rozwiązanie f(n) = n(n+1)/2 spełnia równanie funkcyjne f(n) = f(n-1) + n

   f(n-1) + n = (n-1)n/2 + n = ((n-1)n + 2n)/2 = n(n+1)/2 = f(n)

Zadanie 2

Udowodnij poprawność rozwiązania równania rekurencyjnego:

       4           ; n = 1
f(n) =
       8 + 2f(n/2) ; n = 2k ∧ k ∈ N \ {0}

Rozwiązanie:

f(n) = 12n - 8

Dowód indukcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Z: f(n) = 12n - 8
   T: f(2n) = 12*2n - 8
   
Dowód:

   f(2n) = * = 8 + 2f(n) = ** = 8 + 2(12n - 8) = 8 + 2*12n - 2*8 = 12*2n - 8
   
*  korzystamy z równania
** korzystamy z założenia

Dowód funkcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Wykażemy, że rozwiązanie f(n) = 12n - 8 spełnia równanie funkcyjne f(n) = 8 + 2f(n/2)

   Z: n = 2k ∧ k ∈ N \ {0}

   8 + 2f(n/2) = 8 + 2(12(n/2) - 8) = 2*12(2k/2) - 8 = 2*12*2k-1 - 8 = 12*2k - 8 = 12n - 8 = f(n)

Zadanie 3

Udowodnij poprawność rozwiązania równania rekurencyjnego:

       4                       ; n = 1
f(n) =
       8 + f((n+1)/2) + f(n/2) ; n > 1             Uwaga: / to dzielenie bez reszty

Rozwiązanie:

f(n) = 12n - 8

Dowód indukcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Z: f(n) = 12n - 8
   T: f(n+1) = 12(n + 1) - 8
   
Dowód:

   f(n+1) = 8 + f((n+2)/2) + f((n+1)/2) = 8 + 12((n+2)/2) - 8 + 12((n+1)/2) - 8 = 12((n+2)/2) + 12((n+1)/2) - 8 = *

Z1: n + 1 = 2k

        * =  12((2k+1)/2) + 12((2k)/2) - 8 = 12k + 12k - 8 = 12*2k - 8 = 12(n + 1) - 8

Z2: n + 1 = 2k + 1

        * =  12((2k+2)/2) + 12((2k+1)/2) - 8 = 12(k+1) + 12k - 8 = 12(2k+1) - 8 = 12(n + 1) - 8

Dowód funkcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Wykażemy, że rozwiązanie f(n) = 12n - 8 spełnia równanie funkcyjne f(n) = 8 + f((n+1)/2) + f(n/2)

Z1: n = 2k

   8 + f((2k+1)/2) + f(2k/2) = 8 + f(k) + f(k) = 8 + 12k - 8 + 12k - 8 = 12*2k - 8 = 12n - 8 = f(n)

Z2: n = 2k + 1

   8 + f((2k+2)/2) + f((2k+1)/) = 8 + f(k+1) + f(k) = 8 + 12k + 12 - 8 + 12k - 8 = 12(2k+1) - 8 = 12n - 8 = f(n)

Zadanie 4

Udowodnij, że ciąg {an} przyjmuje wartości naturalne, gdzie:

an = (2 + √3)n + (2 - √3)n

Tw. 1

Z: n ∈ N
T: an ∈ N

Dowód indukcyjny

1. n = 1
   a1 = (2 + √3)1 + (2 - √3)1 = 4 ∈ N

2. Z: an ∈ N
   T: an+1 ∈ N
   
Dowód:

   an+1 = (2 + √3)n+1 + (2 - √3)n+1 = (2 + √3)n⋅(2 + √3) + (2 - √3)n⋅(2 - √3)
   
   an+1 = 2((2 + √3)n + (2 - √3)n) + √3(2 + √3)n - √3(2 - √3)n

   Niech:

   bn = √3(2 + √3)n - √3(2 - √3)n   jeżeli bn ∈ N to an+1 ∈ N

   Tw. 2

   Z: n ∈ N
   T: bn ∈ N

   Dowód indukcyjny

   1. n = 1
      b1 = √3(2 + √3)1 - √3(2 - √3)1 = 6 ∈ N

   2. Z: bn ∈ N
      T: bn+1 ∈ N

   Dowód:

      bn+1 = √3(2 + √3)n+1 - √3(2 - √3)n+1 = √3(2 + √3)n⋅(2 + √3) - √3(2 - √3)n⋅(2 - √3)

      bn+1 = 3(2 + √3)n + 3(2 - √3)n + 2√3(2 + √3)n - 2√3(2 - √3)n

      bn+1 = 3((2 + √3)n + (2 - √3)n) + 2(√3(2 + √3)n - √3(2 - √3)n) ∈ N  bo  an ∈ N ∧ bn ∈ N

   an+1 = 2((2 + √3)n + (2 - √3)n) + √3(2 + √3)n - √3(2 - √3)n ∈ N  bo  an ∈ N ∧ bn ∈ N

Strona główna