Funkcja tworząca, wzór jawny, grafy. mod

Crave · Post autor: **Crave** » 11 wrz 2014, o 17:40

Witam serdecznie. Potrzebuję pomocy w wytłumaczeniu jak rozwiązuje się takie zadania (tak na chłopski rozum).

Zadanie 1.
Przy użyciu funkcji tworzących wyznaczyć wzór jawny na n-ty wyraz ciągu
\(\displaystyle{ a_{0} =2, a_{1}=3, a_{n}=5_{a_{n-1}}+6_{a_{n-2}}, n \ge 2}\)

Zadanie 2.
Udowodnić, że jeśli graf T jest drzewem o n wierzchołkach to T ma n-1 krawędzi.

Zadanie 3.
Czy \(\displaystyle{ 3^{40}+5 ^{40} = 4 (mod 7)}\)

Zadanie 4.
Wyznacz \(\displaystyle{ x,y \in Z}\) takie, że (595,459)=595k+459j

Nie proszę o rozwiązania, tylko o wytłumaczenie w jaki sposób rozwiązuje się takie zadania (chociaż nie ukrywam... rozwiązania w zrozumieniu mogą być całkiem pomocne). Jeżeli ktoś znajdzie wolną chwilkę i pomoże z choćby jednym zadaniem z powyższych to będę bardzo wdzięczny.

Pozdrawiam!

miodzio1988 · Post autor: **miodzio1988** » 11 wrz 2014, o 17:45

A moze tak sam poszukasz schematow rozwiązań?

369890.htm

temat zaraz pod Twoim...

Crave · Post autor: **Crave** » 11 wrz 2014, o 17:47

Szukałem wcześniej, a dopiero teraz założyłem temat. Wtedy go jeszcze nie było. Faktycznie. No to jedno zadanie. Jeszcze 3 ^^

miodzio1988 · Post autor: **miodzio1988** » 11 wrz 2014, o 17:48

Szukaj zatem dalej, kazdy typ zadania znajdziesz na forum

Marcinek665 · Post autor: **Marcinek665** » 11 wrz 2014, o 17:49

Zadanie 1 odkopałem przed chwilą sprzed czterech dni, więc minimalnie rozumiem.
Zadanie 2: narysuj to sobie i popatrz, co się dzieje.
Zadanie 3: tutaj https://www.matematyka.pl/369695.htm
Zadanie 4: algorytm euklidesa.

Crave · Post autor: **Crave** » 11 wrz 2014, o 17:54

2. Wiem co się dzieje, wiem jak to wygląda. Nie wiem jak zapisać rozwiązania takich przypadków, żeby było zaliczone jako odpowiedź na egzaminie.

Marcinek665 · Post autor: **Marcinek665** » 11 wrz 2014, o 18:12

To napisz taki dowód jaki wymyśliłeś i stwierdzimy czy się nadaje

Crave · Post autor: **Crave** » 11 wrz 2014, o 18:43

Zdanie "nie wiem jak zapisać" raczej równoznaczne jest z tym, że nie mam żadnego dowodu, bo nie wiem jak to wytłumaczyć. To co widać na grafie drzewie jest oczywiste. Są wierzchołki i liczba krawędzi zawsze jest mniejsza o jeden od liczby wierzchołków.

Czy może najprościej skorzystać z zasady indukcji matematycznej?

Niech Dn będzie dowolnym drzewem, które ma n krawędzi.
Stosujemy zasadę indukcji. Sprawdzamy warunki 1 i 2.
Warunek 1
Dla n = 1 drzewo ma tylko jedną krawędź i dwa wierzchołki. Jest tylko jedno takie drzewo. Założenie indukcyjne jest więc spełnione dla n0.= 1.
Warunek 2
Drzewo Dn ma co najmniej jeden wierzchołek końcowy. Gdy odetniemy ten wierzchołek i przylegającą do niego krawędź, otrzymamy inne drzewo Dn-1. Z założenia indukcyjnego dla drzewa Dn-1 jest prawdą, że liczba wierzchołków jest o jeden większa od liczby krawędzi. Tak jest też dla drzewa Dn.
Na mocy zasady indukcji zdanie "Dla każdego drzewa liczba wierzchołków drzewa jest o jeden większa niż liczba jego krawędzi" zostało w całej pełni udowodnione.

Czy taki dowód będzie wystarczający?-- 13 wrz 2014, o 13:52 --Oficjalnie nie jestem przekonany do powyższego dowodu, bo w sumie nie dowodzi, że T ma n-1 krawędzi. Proszę kogoś jeszcze o zajrzenie do tego tematu i pomoc z tym zadaniem.