Indukcja matematyczna i relacje

[adamus132]

Witam, mam problem z rozwiazaniem kilku zadan z dyskretnej do egzaminu oto one:

Zad1 W zbiorze słów 5-cio bitowych określono relację S w ten sposób, że xSy wtedy i tylko wtedy, gdy y powstaje z x przez cykliczne przesunięcie słowa x o jeden bit w prawo (np. 10011 S 11001). Niech R będzie równoważnościowym domknięciem S (czyli R = p(s(z(S))).
(a) Wyznacz liczby elementów klas abstrakcji wyznaczonych przez następujących reprezentantów:
| [00000]R| = .......... | [01001]R| = .......... | [10101]R| = ..........
(b) Wypisz po jednym reprezentancie każdej z klas abstrakcji relacji R.

Zad 2 Dany jest ciąg a1 = 2 oraz an+1 = (an + 3)2 + 5, dla n > 1. Na odwrocie kartki udowodnij, że dla kazdego n nalezacego do N (7 | (an + 5)).

Zad 3 W zbiorze słów 5-cio bitowych określono relację S w ten sposób, że xSy wtedy i tylko wtedy, gdy y powstaje z x przez zamianę dwóch sąsiednich bitów. (np. 10011 S 10101). Niech R będzie równoważnościowym domknięciem S (czyli R = p(s(z(S))).
(a) Wyznacz liczbę elementów klas abstrakcji wyznaczonych przez następujących reprezentantów:
| [00000]R| = .......... | [01001]R| = .......... | [11101]R| = ..........
(b) Wypisz po jednym reprezentancie każdej z klas abstrakcji relacji R.

Zad 4 Digraf G1 reprezentuje relację S. Niech R = p(z(S)).
przedstaw diagram Hassego relacji R.
http://i41.tinypic.com/feo3sz.png
okresl wysokosc i szerokosc

Zad 5 Wyznacz zwarty wzór na n-ty wyraz ciągu określonego rekurencyjnie: a1 = 7 oraz an+1 = an + 2n + 1. Przedstaw wzór poniżej, a jego wyprowadzenie (w przypadku odgadnięcia – dowód poprawności) na odwrocie strony.

Z gory dziekuje za pomoc.

[radagast]

Witam, mam problem z rozwiazaniem kilku zadan z dyskretnej do egzaminu oto one:

Zad 2 Dany jest ciąg a1 = 2 oraz an+1 = (an + 3)2 + 5, dla n > 1. Na odwrocie kartki udowodnij, że dla kazdego n nalezacego do N (7 | (an + 5)).

Po prostu indukcyjnie:
dla n=1: \(a_n+5=a_1+5=2+5=7\ \ \ 7|7\ ok\)

zał ind:
istnieje \(n \in N:\) t.że \(7|a_n+5\)
czyli
istnieje \(n \in N:\) istnieje \(k \in C: a_n+5 =7k\)
czyli
istnieje \(n \in N:\) istnieje \(k \in C: a_n =7k-5\)


pokażemy że wtedy \(7|a_{n+1}+5\)
czyli
istnieje \(l \in C: a_{n+1}+5 =7l\)


dowód
\(a_{n+1}+5= (a_n+3)^2+5+5=(7k-5+3)^2+10=(7k-2)^2+10=49k^2-28k+14=7(7k^2-4k+2)\)

no to istotnie, istnieje \(l \in C,\ \ l=7k^2-4k+2\)

CBDO