Matematyka.pl

Mam taki wzór (oznacza liczbę słów o określonych warunkach nad pewnym alfabetem):
\(\displaystyle{ S _{n}=n+1}\)
nie wiem jak powinien wyglądać dowód takiego zbioru.
Czy tak jest dobrze? (2 etap dowodu)

Zakładamy, że \(\displaystyle{ k \in A}\), Sprawdzamy, czy \(\displaystyle{ k+1 \in A}\)
\(\displaystyle{ S _{k} = k+1\\
S _{k+1} = (k+1)+1\\
S _{k+1} = k+2}\)

To chyba nie tak, ale nie wiem jak można to inaczej rozpisać.

Scrub pisze:Mam taki wzór (oznacza liczbę słów o określonych warunkach nad pewnym alfabetem):
\(\displaystyle{ S _{n}=n+1}\)
nie wiem jak powinien wyglądać dowód takiego zbioru.

Co to jest "dowód zbioru"?

Scrub pisze:Zakładamy, że \(\displaystyle{ k \in A}\), Sprawdzamy, czy \(\displaystyle{ k+1 \in A}\)

Czym jest \(\displaystyle{ A}\) ?

Scrub pisze:\(\displaystyle{ S _{k} = k+1\\
S _{k+1} = (k+1)+1\\
S _{k+1} = k+2}\)

To chyba nie tak, ale nie wiem jak można to inaczej rozpisać.

Ale co Ty chcesz w ogóle dowieść?

JK

Co to jest "dowód zbioru"?

Pomyliłem się, powinno być dowód wzoru.

Sprawa wygląda tak:
Mam alfabet \(\displaystyle{ = \{a, b\}}\)
\(\displaystyle{ S _{n}}\) oznacza liczbę wszystkich słów długości \(\displaystyle{ n}\), które nie zawierają podsłowa \(\displaystyle{ ab}\)
Czyli \(\displaystyle{ aaa}\), \(\displaystyle{ baa}\) jest ok, a \(\displaystyle{ bab}\) już nie.
Takich słów od długości \(\displaystyle{ n}\) jest zawsze \(\displaystyle{ n+1}\).
Więc \(\displaystyle{ S _{n}=n+1}\) i muszę to udowodnić indukcyjnie.
Czyli standardowo \(\displaystyle{ A = \{n \in N : S _{n}=n+1\}}\)
1. Sprawdzam, czy \(\displaystyle{ 0 \in A}\) i należy
2. Zakładam, że \(\displaystyle{ k \in A}\), sprawdzam czy \(\displaystyle{ k + 1 \in A}\)
Problem jest w tym miejscu. Wydaje mi się, że ten dowód co napisałem jest bez sensu.

Nie jest to dowód oraz istotnie jest bez sensu.

Chcesz dowieść, że \(\displaystyle{ S _{n}=n+1}\). W tym celu musisz przeprowadzić rozumowanie indukcyjne, ale ono dotyczy słów i to na słowach operujesz.

Musisz pokazać:
1. Są \(\displaystyle{ 2}\) słowa długości \(\displaystyle{ 1}\).
2. Ustalasz dowolne \(\displaystyle{ n\in\NN}\) takie, że słów długości \(\displaystyle{ n}\) jest \(\displaystyle{ n+1}\) i musisz udowodnić, że słów długości \(\displaystyle{ n+1}\) jest \(\displaystyle{ n+2}\). W tym celu zastanawiasz się, w jaki sposób słowa długości \(\displaystyle{ n+1}\) powstają ze słów długości \(\displaystyle{ n}\).

JK

Każde następny zbiór słów powstaje przez: dodanie do jednego ze słów z poprzedniego zbioru litery a i przez dodanie b do wszystkich słów. Mam to nawet rozrysowane i rozpisane, ale nie wiem jak to zrobić indukcyjnie.

1.
Zbiór słów długości 0: \(\displaystyle{ \{\epsilon\}}\)
\(\displaystyle{ S_{0} = 1}\)

Zbiór słów długości 1: \(\displaystyle{ \{a, b\}}\)
\(\displaystyle{ S_{1} = 2}\)

2.
Teraz nie wiem jak to udowodnić. Udowodniłem słownie jak wyżej ale nie wiem jak to zrobić indukcją.

Jan Kraszewski pisze:2. Ustalasz dowolne \(\displaystyle{ n\in\NN}\) takie, że "legalnych" słów długości \(\displaystyle{ n}\) jest \(\displaystyle{ n+1}\) i musisz udowodnić, że "legalnych" słów długości \(\displaystyle{ n+1}\) jest \(\displaystyle{ n+2}\).

Każde słowo "legalne" długości \(\displaystyle{ n+1}\) powstaje z "legalnego" słowa długości \(\displaystyle{ n}\) poprzez dopisanie na końcu jednego symbolu (istotnie, jeśli słowo dłuższe jest "legalne", to po skreśleniu ostatniego symbolu nadal jest "legalne"). Słowa "legalne" długości \(\displaystyle{ n}\) albo kończą się na \(\displaystyle{ a}\), albo na \(\displaystyle{ b}\). Jest tylko jedno słowo kończące się na \(\displaystyle{ a}\) - składające się z samych \(\displaystyle{ a}\) (dlaczego?). W związku z tym jest \(\displaystyle{ n}\) słów długości \(\displaystyle{ n}\) kończących się na \(\displaystyle{ b}\). Do słowa kończącego się na \(\displaystyle{ a}\) mogę dopisać \(\displaystyle{ a}\) lub \(\displaystyle{ b}\), do słów kończących się na \(\displaystyle{ b}\) - tylko \(\displaystyle{ b}\). W związku z tym "legalnych" słów długości \(\displaystyle{ n+1}\) jest \(\displaystyle{ 2+n}\), co kończy dowód kroku indukcyjnego.

Ale i tak wydaje się, że prościej udowodnić ten wzór bez indukcji, po prostu opisując zbiór tych słów i uzasadniając, że musi właśnie tak wyglądać.

JK