Jak FORMALNIE udowodnić że poniższy algorytm zwraca 1 dla n = 1 a 0 w pozostałych przypadkach? Będę bardzo wdzięczny za wszelkie podpowiedzi
function K( n: word): word;
begin
if (n < 2) then K := n
else K := K(n − 1) * K(n − 2);
end;
Będę bardzo wdzięczny za wszelkie podpowiedzi
Indukcja matematyczna.
K(n) = K(n-1) * K(n-2) = K(n-2) * K(n-3) * K (n-3) * K(n-4) = K(n-3) * K(n-4) * K(n-4) * K(n-5) * K(n-4) * K(n-5) * K(n-5) * K(n-6) = ...
ale to do niczego nie prowadzi
Prowadzi do tego, że na samym końcu masz
K(n-1)K(n-2)...*K(1)*K(0) = K(n-1)K(n-2)...*0 = 0
cnd.
Trudno jest to udowodnić, bo dla liczb ujemnych się nie zgadza.
Tw. indukcyjne: K(n) = 0 dla n>=2.
Wpierw sprawdzamy dla n=2: K(2) = K(1)K(0) = 10 =0.
Krok indukcyjny: zakładamy, że K(n) = 0, K(n+1) = K(n)K(n-1) = 0K(n-1) = 0.