Rownianie rekurencyjne

[andrzej258]

Mam zadanie z szachownica o wymiarach 1 na n. Kolorujemy ja na niebiesko i czerwono. pola obok siebie nie moga byc czerwone a niebieskie moga. Mam znalesc T(n) ktore jest liczba mozliwych kolorowan.
a)Znadź dla T(n) zalezność rekurencyjna.
b) wyznaczyc postac zwarta dla T(n)

\(\displaystyle{ T(1)=2 \begin{cases} c \\ n \end{cases}}\)
\(\displaystyle{ T(2)=3 \begin{cases} cn \\ nc\\nn \end{cases}}\)
\(\displaystyle{ T(3)=5 \begin{cases} cnn \\ ncn\\nnn\\cnc\\nnc \end{cases}}\)
\(\displaystyle{ T(4)=8 \begin{cases} cnnn \\ ncnn\\nnnn\\cncn\nncn\\cnnc\\ncnc\\nnnc \end{cases}}\)

Widac ze tworzy to ciag fibonaciego wiec

\(\displaystyle{ T(n)=T(n-1)+T(n-2)}\)

wiec korzystajac z twierdzenia Eulera-Bineta mozna wyznaczyc postac zwarta:

\(\displaystyle{ F(n)=\frac{1}{ \sqrt{5} } \left( \frac{1+ \sqrt{5} }{2} \right) ^{n}-\frac{1}{ \sqrt{5} } \left( \frac{1- \sqrt{5} }{2} \right) ^{n}}\)

Nasz ciag jest ciagiem fibonnaciego przesunietym o jeden wiec postac zwarta wynosi:

\(\displaystyle{ F(n+1)=\frac{1}{ \sqrt{5} } \left( \frac{1+ \sqrt{5} }{2} \right) ^{n+1}-\frac{1}{ \sqrt{5} } \left( \frac{1- \sqrt{5} }{2} \right) ^{n+1}}\)

A teraz jaki jest problem, poniewaz nie doszedlem do tego za pomoca rownan rekurencyjnych a prawdępowiedziawszy nie wiem jak to zrobic to czy moglby mi powiedziec jak to zrobic?

[octahedron]

Jeśli \(\displaystyle{ n}\)-te pole jest czerwone, to \(\displaystyle{ n+1}\) może być tylko niebieskie, czyli \(\displaystyle{ T(n+1)=T(n)}\), wtedy \(\displaystyle{ n+2}\) może być czerwone lub niebieskie, zatem \(\displaystyle{ T(n+2)=2T(n+1)=T(n+1)+T(n)}\). Jeśli \(\displaystyle{ n}\)-te pole jest niebieskie, to następne może być czerwone lub niebieskie, czyli \(\displaystyle{ T(n+1)=2T(n)}\), a wtedy \(\displaystyle{ T(n+2)=2T(n)+T(n)=T(n+1)+T(n)}\). W obu przypadkach pasuje wzór \(\displaystyle{ T(n+2)=T(n+1)+T(n)}\)

[andrzej258]

Tylko teraz czy dobrze obliczylem postac zwarta ze jest to ciag przesuniety o 1 czy o 2?

[octahedron]

Jest przesunięty o \(\displaystyle{ 2}\). Zresztą można to policzyć:

\(\displaystyle{ T(1)=2\\\\
T(2)=3\\\\
T(n+2)=T(n+1)+T(n)\\\\
T(n+2)-T(n+1)-T(n)=0\\\\
q^2-q-1=0\\\\
q_1=\frac{1-\sqrt{5}}{2}\\\\
q_2=\frac{1+\sqrt{5}}{2}\\\\
T(n)=C_1q_1^n+C_2q_2^n\\\\
\begin{cases}T(1)=C_1 \cdot \frac{1-\sqrt{5}}{2}+C_2\cdot\frac{1+\sqrt{5}}{2}=2\\T(2)=C_1 \cdot \left( \frac{1-\sqrt{5}}{2}\right) ^2+C_2\cdot\left( \frac{1+\sqrt{5}}{2}\right) ^2=3\end{cases}\\\\
C_1=\frac{\sqrt{5}-3}{2\sqrt{5}}\\\\
C_2=\frac{\sqrt{5}+3}{2\sqrt{5}}\\\\
T(n)=\frac{\sqrt{5}-3}{2\sqrt{5}}\cdot \left( \frac{1-\sqrt{5}}{2}\right)^n+\frac{\sqrt{5}+3}{2\sqrt{5}}\cdot \left( \frac{1+\sqrt{5}}{2}\right) ^n}\)

[andrzej258]

Mam jeszcze jedno pytanie. Jak wytlumaczyc dlaczego równanie charakterystyczne ma postac \(\displaystyle{ q^{2}-q-1=0}\)??

[octahedron]

Jeśli założymy rozwiazanie postaci \(\displaystyle{ T(n)=Cq^n}\), to mamy:

\(\displaystyle{ T(n+2)-T(n+1)-T(n)=0\\\\
Cq^{n+2}-Cq^{n+1}-Cq^{n}=0\\\\
Cq^{n}(q^2-q-1)=0\\\\
q^2-q-1=0\\\\}\)