Zad01_indukcja.doc

[DM 01]

[1/01] Stosując indukcję:

(1) wykaż poprawność wzorów na sumę szeregu arytmetycznego i geometrycznego.

(2) wykaż, że n Î N Þ 6 | n(n + 1)(2n + 1) (a | b czytaj "a dzieli b" lub "b jest podzielne przez a")

(3) wykaż, że n Î NP Þ 4 | 1 + 3n (NP - zbiór naturalnych liczb nieparzystych)

(4) wykaż, że n Î NP Þ 5 | 2n + 3n

(5) wykaż, że jeżeli wyrazy ciągu an spełniają warunki: a1 = 1, a2 = 2, an = an-1 + an-2, to an < (7/4)n.

(6) wykaż, że jeżeli wyrazy ciągu an spełniają warunek: an = an-1 / (2an-1 + 1), to an = a0 / (2na0 + 1).

(7) wykaż, że  m5 / 5 + m3 / 3 + 7m / 15 jest liczbą całkowitą dla każdego całkowitego m.

[2/01] Dowieść, że dla dodatnich, rzeczywistych a1,...,an mamy:

·     an/a1+ai / ai+1 ³ n,

·     jeżeli a1...an = 1, to ³ n,

·     zawsze (a1...an)1/n £ (a1+...+an)/n. Kiedy zachodzi równość?

[3/01]

const

   k = ...;

type

  T = array[1..k] of integer;

for i = 1 to k – 1 do

   if T[i] < T[i+1] then "zamień T[i] z T[i + 1]"

writeln(T[k]);

Udowodnij, że powyższy algorytm w pseudo-pascalu wypisuje maksymalną wartość tablicy T. (Wskazówka: Zastosuj indukcję względem i. Zastosuj predykat P(i) Û "po wykonaniu i - tego kroku pętli element maksymalny znajduje się w polu tablicy o indeksie większym niż i").

[4/01]

const

   k = ...;

type

  T = array[1..k] of integer;

for i = 1 to k – 1 do

   for j = 1 to k – i do

      if T[j] < T[j+1] then "zamień T[j] z T[j + 1]"

Udowodnij, że powyższy algorytm w pseudo-pascalu sortuje tablicę T. (Wskazówka: Zastosuj indukcję względem i. Skorzystaj z zadnia poprzedniego. Określ wyraźnie predykat P, który występuje w Twoim dowodzie (zapewne inny niż w poprzednim zadaniu)).

[5/01] W mieście Skrzyżne nie ma ślepych ulic (tzn. jadąc dowolną ulicą w dowolnym kierunku zawsze dojedziemy do skrzyżowania) i wszystkie ulice są dwukierunkowe. Do każdego skrzyżowania dochodzi parzysta liczba ulic. Z każdego skrzyżowania można dojechać do każdego innego skrzyżowania. Udowodnij, że można w tym mieście przejechać wszystkie ulice tak, aby każdą ulicą jechać tylko jeden raz, rozpoczynając i kończąc podróż na tym samym skrzyżowaniu. (Wskazówka: zastosuj indukcję względem liczby ulic. Skorzystaj z silniejszej wersji zasady indukcji matematycznej (krok indukcyjny: [P(s) Ù P(s + 1) Ù ... Ù P(n)] ® P(n + 1)).

[6/01] Pokaż, że dla dowolnej liczby naturalnej n istnieje liczba naturalna cn taka, że jeżeli połączymy odcinkami każde dwa wierzchołki k-kąta foremnego, gdzie k ³ cn, to przy dowolnym pokolorowaniu wszystkich tych odcinków n kolorami pewne trzy odcinki będące bokami jednego trójkąta uzyskają ten sam kolor.

[7/01] Które z poniższych implikacji logicznych są prawdziwe. Dla każdej nieprawdziwej implikacji przedstaw kontrprzykład dokładnie definiując predykat P.

q       [P(1) Ù "nÎN(P(n2) ® P(n2 + 1)) Ù "nÎN(P(n + 1) ® P(n))] Þ "nÎN(P(n))

q       [P(125) Ù "nÎN(P(n2) ® P(n2 + 2n + 2)) Ù "nÎN(P(n + 1) ® P(n))] Þ "nÎN(P(n))

[8/01]

(a) Udowodnij, że poniższy program wypisuje wyłącznie liczby całkowite.

x := 1;

while (1 < 2) do

  begin

    writeln(x);

    x := ;

  end;

(b) Udowodnij, że następujący program wypisuje wyłącznie liczby całkowite.

x = 1;

while (1 > 0)

{

              print(x);

}

[9/01] Dany jest ciąg określony rekurencyjnie:

Udowodnij, że ~$nÎN (3 | an).

[10/01] Dany jest ciąg określony rekurencyjnie:

Udowodnij, że "nÎN (4 | (an + 1)2 – 1).

[11/01] Ciąg an określony jest rekurencyjnie:

a1 = 1, a2 = 1,

an+2 = an+1 + an, dla n Î N.

Udowodnij, że "nÎN(5 | a5n).