Równanie

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

Rozwiązanie

f(n) = 1 + n

Uwaga

Funkcja f(n) = 1 + n jest rozwiązaniem równania rekurencyjnego f wtedy i tylko wtedy,
gdy dla każdego n z dziedziny równania rekurencyjnego f wartość wyliczona z funkcji f(n)
jest równa wartości uzyskanej z rozwijania równania rekurencyjnego f. Dla przykładu przyjmijmy:

n = 3

f(3) = 1 + 3 = 4

f(3) = 1 + f(2) = 1 + 1 + f(1) = 1 + 1 + 1 + f(0) = 1 + 1 + 1 + 1 = 4

Dowód indukcyjny

1. f(0) = 1
   f(0) = 1 + 0 = 1
   
2. Z: f(n) = 1 + n
   T: f(n+1) = 1 + (n+1) = 2 + n
   
Dowód:

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

Dowód funkcyjny

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

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

Rozwiązywanie równań

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

Sposób I

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

Sposób II

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

Z: n - k = 0  =>  k = n

   * = 1 + 1 + 1 + 1 + ... + f(n-k) = k + f(n-k) = n + f(0) = n + 1 = 1 + n

Zadanie 0

Dana jest liczba postaci n = 2^p, gdzie p ∈ N ∪ {0}. Ile razy należy kolejno dzielić n bez reszty przez 2, aby uzyskać 1?

1 = 20            0 razy
2 = 21 / 21 = 1   1 raz
4 = 22 / 22 = 1   2 razy
8 = 23 / 23 = 1   3 razy
...
n = 2p / 2p = 1   p razy

Aby uzyskać 1, liczbę n należy kolejno dzielić bez reszty przez 2 log₂(n) razy.

n = 8  =>  log2(n) = 3

8/2  4/2  2/2  1

Rozwiązanie sprowadza się do wyznaczenia rozwiązania równania rekurencyjnego:

       0          ; n = 1
f(n) =
       1 + f(n/2) ; n > 1 ∧ n = 2k, k ∈ N

Zadanie 00

Dana jest liczba postaci n = 2^p + q, gdzie 0 <= q < 2^p ∧ p ∈ N ∪ {0}. Ile razy należy kolejno dzielić n bez reszty przez 2, aby uzyskać 1?

1 =  20                 0 razy
2 =  21      / 21 = 1   1 raz
3 = (21 + 1) / 21 = 1   1 raz
4 =  22      / 22 = 1   2 razy
5 = (22 + 1) / 22 = 1   2 razy
6 = (22 + 2) / 22 = 1   2 razy
7 = (22 + 3) / 22 = 1   2 razy
8 =  23      / 23 = 1   3 razy
...
n = (2p + q) / 2p = p    p razy

Aby uzyskać 1, liczbę n należy kolejno dzielić bez reszty przez 2 [log₂(n)] razy.

n = 10  =>  [log2(n)] = 3

10/2  5/2  2/2  1

Rozwiązanie sprowadza się do wyznaczenia rozwiązania równania rekurencyjnego:

       0          ; n = 1
f(n) =
       1 + f(n/2) ; n > 1 ∧ n ∈ N

Zadanie 1

Rozwiąż równanie rekurencyjne:

       0          ; n = 1
f(n) =
       1 + f(n/2) ; n > 1 ∧ n = 2k, k ∈ N

Sposób I

f(1) = f(20) = 0
f(2) = f(21) = 1 + f(1) = 1
f(4) = f(22) = 1 + f(2) = 1 + 1
f(8) = f(23) = 1 + f(4) = 1 + 1 + 1
...
f(n) = f(2k) = 1 + f(n/2) = k

Z: n = 2k ∧ k ∈ N ∪ {0}  =>  k = log2(n)

f(n) = log2(n)

Sposób II

f(n) = 1 + f(n/2) = 1 + 1 + f(n/4) = 1 + 1 + 1 + f(n/8) = 1 + 1 + 1 + 1 + f(n/16) = ... = *

Z: n/2k = 1  =>  n = 2k  =>  k = log2(n)

   * = 1 + 1 + 1 + 1 + ... + f(n/2k) = k + f(n/2k) = log2(n) + f(1) = log2(n)

Dowód indukcyjny

1. f(1) = 0
   f(1) = log2(1) = 0
   
2. Z: f(n) = log2(n)
   T: f(2n) = log2(2n)

Dowód:

   f(2n) = * = 1 + f(n) = ** = 1 + log2(n) = log2(2) + log2(n) = log2(2n)

*  korzystamy z równania
** korzystamy z założenia

Dowód funkcyjny

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

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

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

Zadanie 000

Równanie rekurencyjne:

       0          ; n = 1
f(n) =
       1 + f(n/2) ; n > 1 ∧ n = 2k, k ∈ N

Rozwiązanie:

f(n) = log2(n)

Równanie rekurencyjne:

       a          ; n = 1
f(n) =
       b + f(n/2) ; n > 1 ∧ n = 2k, k ∈ N

Rozwiązanie:

f(n) = a + b*log2(n)

Dowód funkcyjny

1. f(1) = a
   f(1) = a + log2(1) = a

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

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

   b + f(n/2) = b + a + b*log2(n/2) = b + a + b*log2(n) - b*log2(2) = a + b*log2(n) = f(n)

Zadanie 2

Uzasadnij, że równanie:

n = 2p + q ∧ n ∈ N \ {0} ∧ p, q ∈ N ∪ {0}

przy założeniu:

0 <= q < 2p

ma dokładnie jedno rozwiązanie ze względu na zmienne p i q.

Dowód:

Z:  0 <= q < 2p

    2p <= 2p + q < 2p+1
    2p <= n < 2p+1
    p <= log2(n) < p+1
    p = [log2(n)]

    n = 2p + q
    q = n - 2p
    q = n - 2[log2(n)]

Rozwiązanie:

    p = [log2(n)]
    q = n - 2[log2(n)]

Zadanie 3

Rozwiąż równanie:

n = 2p + q ∧ n ∈ N \ {0} ∧ p, q ∈ N ∪ {0}

przy założeniu 0 <= q < 2^p dla n = 52.

	20	21	22	23	24	25	26	27	28	29	210	...
n:	1	2	4	8	16	32	64	128	256	512	1024	...
log2(n):	0	1	2	3	4	5	6	7	8	9	10	...

Na podstawie tabeli:

32 < 52 < 64

Funkcja log₂(n) jest rosnąca:

log2(32) < log2(52) < log2(64)
5 < log2(52) < 6
5 = [log2(52)]

Zatem:

p = [log2(52)] = 5
q = 52 - 25 = 52 - 32 = 20

52 = 25 + 20 ∧ 0 <= 20 < 25

Zadanie 4

Rozwiąż równanie rekurencyjne:

       0          ; n = 1
f(n) =
       1 + f(n/2) ; n > 1 ∧ n ∈ N

Sposób I

f(1) = f(20)     = 0
f(2) = f(21)     = 1 + f(1) = 1
f(3) = f(21 + 1) = 1 + f(1) = 1
f(4) = f(22)     = 1 + f(2) = 1 + 1
f(5) = f(22 + 1) = 1 + f(2) = 1 + 1
f(6) = f(22 + 2) = 1 + f(3) = 1 + 1
f(7) = f(22 + 3) = 1 + f(3) = 1 + 1
f(8) = f(23)     = 1 + f(4) = 1 + 1 + 1
...
f(n) = f(2p + q) = 1 + f(n/2) = p

Z: n = 2p+q ∧ 0 <= q < 2p

Mamy:

0 <= q < 2p
2p <= 2p+q < 2p+1
2p <= n < 2p+1
p <= log2(n) < p+1
p = [log2(n)]

f(n) = [log2(n)]

Sposób II

Z: n = 2p+q ∧ 0 <= q < 2p  =>  p = [log2(n)]

f(n) = 1 + f(n/2) = 1 + f((2p+q)/2) = 1 + 1 + f((2p+q)/22) = 1 + 1 + 1 + f((2p+q)/23) =

     = ... = p + f((2p+q)/2p) = p + f(1) = p = [log2(n)]

Dowód indukcyjny

1. f(1) = 0
   f(1) = [log2(1)] = 0
   
2. Z: f(n) = [log2(n)]
   T: f(n+1) = [log2(n+1)]
   
Dowód:

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

Z1: n + 1 = 2k ∧ k ∈ N \ {0}

        * = 1 + f(2k/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2((n+1)/2)] = 1 + [log2(n+1) - log2(2)] = [log2(n+1)]

Z2: n + 1 = 2k + 1 ∧ k ∈ N \ {0}

        * = 1 + f((2k+1)/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2(n/2)] = 1 + [log2(n) - log2(2)] =
          = [log2(n)] = ** = [log2(n+1)]
          
** Lemat

   Z: n = 2k ∧ k ∈ N \ {0}
   T: [log2(n)] = [log2(n+1)]
   
Dowód:

   n = 2p+q ∧ 0 <= q < 2p
              2p <= 2p+q < 2*2p
              2p <= n < 2*2p

              2p <= 2k < 2*2p
              2p <= 2k <= 2*2p-2
              
   2p <= 2k < 2k+1 <= 2*2p-1 < 2*2p

   2p <= n < n+1 < 2p+1
   p <= log2(n) < log2(n+1) < p+1
   
   [log2(n)] = [log2(n+1)]

Dowód funkcyjny

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

Z1: n = 2k

   1 + f(2k/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2(n/2)] = 1 + [log2(n) - log2(2)] = [log2(n)] = f(n)

Z2: n = 2k + 1

   1 + f((2k+1)/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2((n-1)/2)] =

                   = 1 + [log2(n-1) - log2(2)] = [log2(n-1)] = * =  [log2(n)] = f(n)

* n-1 jest parzyste, patrz lemat powyżej.

Zadanie 5

Rozwiąż równanie rekurencyjne:

       0              ; n = 0
f(n) =
       1 + f((n-1)/2) ; n > 0 ∧ n = 2k - 1, k ∈ N

Sposób I

f(0)  = f(20 - 1) = 0
f(1)  = f(21 - 1) = 1 + f(0)  = 1
f(3)  = f(22 - 1) = 1 + f(1)  = 1 + 1
f(7)  = f(23 - 1) = 1 + f(3)  = 1 + 1 + 1
f(15) = f(24 - 1) = 1 + f(7)  = 1 + 1 + 1 + 1
f(31) = f(25 - 1) = 1 + f(15) = 1 + 1 + 1 + 1 + 1
...
f(n) = f(2k - 1) = 1 + f((n-1)/2) = k

Z: n = 2k - 1 ∧ k ∈ N ∪ {0}  =>  2k = n + 1  =>  k = log2(n+1)

f(n) = log2(n+1)

Sposób II

Z: n = 2k - 1 ∧ k ∈ N ∪ {0}  =>  2k = n + 1  =>  k = log2(n+1)

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

     = ... = 1 + 1 + ... + f(2k-k - 1) = k + f(0) = log2(n+1)

Dowód indukcyjny

1. f(0) = 0
   f(0) = log2(1) = 1
   
2. Z: f(n) = log2(n+1)
   T: f(2n+1) = log2(2n+2)

Dowód:

   f(2n+1) = * = 1 + f((2n+1-1)/2) = 1 + f(n) = ** = 1 + log2(n+1) = log2(2) + log2(n+1) = log2(2n+2)
   
*  korzystamy z równania
** korzystamy z założenia

Dowód funkcyjny

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

   Z: n = 2k - 1  =>  k = log2(n+1)

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

Zadanie 6

Rozwiąż równanie rekurencyjne:

       0              ; n = 0
f(n) =
       1 + f((n-1)/2) ; n > 0 ∧ n ∈ N

Sposób I

f(0)  = f(20 - 1) = 0
f(1)  = f(20) = 1 + f(0)  = 1
f(2)  = f(21)     = 1 + f(0)  = 1
f(3)  = f(22 - 1) = 1 + f(1)  = 1 + 1
f(4)  = f(22)     = 1 + f(1)  = 1 + 1
f(5)  = f(22 - 1) = 1 + f(2)  = 1 + 1
f(6)  = f(22 - 1) = 1 + f(2) = 1 + 1
f(7)  = f(23 - 1) = 1 + f(3)  = 1 + 1 + 1
f(8)  = f(23    ) = 1 + f(3) = 1 + 1 + 1
f(15) = f(24 - 1) = 1 + f(7)  = 1 + 1 + 1 + 1
f(31) = f(25 - 1) = 1 + f(15) = 1 + 1 + 1 + 1 + 1
...
f(n) = f(2k - 1) = 1 + f((n-1)/2) = k

f(0)  = f(20 - 1) = 0
f(1)  = f(21 - 1) = 1 + f(0)  = 1
f(2)  = f(21)     = 1 + f(0)  = 1
f(3)  = f(22 - 1) = 1 + f(1)  = 1 + 1
f(4)  = f(22)     = 1 + f(1)  = 1 + 1
f(5)  = f(22 + 1) = 1 + f(2)  = 1 + 1
f(6)  = f(22 + 2) = 1 + f(2) = 1 + 1
f(7)  = f(23 - 1) = 1 + f(3)  = 1 + 1 + 1
f(8)  = f(23    ) = 1 + f(3) = 1 + 1 + 1
f(15) = f(24 - 1) = 1 + f(7)  = 1 + 1 + 1 + 1
f(31) = f(25 - 1) = 1 + f(15) = 1 + 1 + 1 + 1 + 1
...
f(n) = f(2k - 1) = 1 + f((n-1)/2) = k

Z: n = 2p+q ∧ 0 <= q < 2p

f(2p+q) = 1 + f((2p+q)/2) = p

Mamy:

0 <= q < 2p
2p <= 2p+q < 2p+1
2p <= n < 2p+1
p <= log2(n) < p+1
p = [log2(n)]

f(n) = [log2(n)]

Sposób II

Z: n = 2p+q ∧ 0 <= q < 2p

f(n) = 1 + f(n/2) = 1 + f((2p+q)/2) = 1 + f(2p-1) = * = 1 + p - 1 = p = ** = [log2(n)]

*  korzystamy z rozwiązania zadania 1
** korzystamy z rozwiązania zadania 2

Dowód indukcyjny

1. f(1) = 0
   f(1) = [log2(1)] = 0
   
2. Z: f(n) = [log2(n)]
   T: f(n+1) = [log2(n+1)]
   
Dowód:

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

Z1: n + 1 = 2k ∧ k ∈ N \ {0}

        * = 1 + f(2k/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2((n+1)/2)] = 1 + [log2(n+1) - log2(2)] = [log2(n+1)]

Z2: n + 1 = 2k + 1 ∧ k ∈ N \ {0}

        * = 1 + f((2k+1)/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2(n/2)] = 1 + [log2(n) - log2(2)] =
          = [log2(n)] = ** = [log2(n+1)]
          
** Lemat

   Z: n = 2k ∧ k ∈ N \ {0}
   T: [log2(n)] = [log2(n+1)]
   
Dowód:

   n = 2p+q ∧ 0 <= q < 2p
              2p <= 2p+q < 2*2p
              2p <= n < 2*2p

              2p <= 2k < 2*2p
              2p <= 2k <= 2*2p-2
              
   2p <= 2k < 2k+1 <= 2*2p-1 < 2*2p

   2p <= n < n+1 < 2p+1
   p <= log2(n) < log2(n+1) < p+1
   
   [log2(n)] = [log2(n+1)]

Dowód funkcyjny

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

Z1: n = 2k

   1 + f(2k/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2(n/2)] = 1 + [log2(n) - log2(2)] = [log2(n)] = f(n)

Z2: n = 2k + 1

   1 + f((2k+1)/2) = 1 + f(k) = 1 + [log2(k)] = 1 + [log2((n-1)/2)] =

                   = 1 + [log2(n-1) - log2(2)] = [log2(n-1)] = * =  [log2(n)] = f(n)

* n-1 jest parzyste, patrz lemat powyżej.

public class Logarytm
{
  public static void main(String[] args)
  {
    int n = 65536;
    
    boolean rowne = true;
    
    for (int i = 1; i <= n; i++)
    {
      if (r(i) != f(i)) rowne = false;
    }
    
    if (rowne) System.out.println("r(n) = f(n) dla n = 1.." + n);
  }
  
  static int r(int n)
  {
    if (n == 1)
    {
      return 0;
    }
    else
    {
      return 1 + r(n/2);
    }
  }
  
  static int f(int n)
  {
    return (int)(Math.log(n) / Math.log(2));
  }
}

r(n) = f(n) dla n = 1..65536
Press any key to continue...

Rozwiąż równania rekurencyjne

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


       f(n/2) + n ; n > 1
f(n) =
       0          ; n = 1


       2f(n/2) + n ; n > 1
f(n) =
       0           ; n = 1


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

       f(-n)           ; n < 0
f(n) = 0               ; n = 0
       f(n-1) + 2n - 1 ; n > 0
       

       f(n/2) + n2 ; n > 1
f(n) =
       0           ; n = 1
       
       
       0              ; n = 1
f(n) =
       f(n-1) + n - 1 ; n > 1
       
       
       f(n/2) + 1 ; n > 1
f(n) = 
       1          ; n = 1
       
       
       3                ; n = 0
f(n) =
       3n + 10 + f(n-1) ; n > 0
       
       
       1              ; n = 1
f(n) =
       f(n-1) + n*2n-1 ; n > 1
       
Wskazówka: a + 2b + 3c + 4d = (a + b + c + d) + (b + c + d) + (c + d) + d