Bardzo proszę o pomoc. Mam równanie:
\(\displaystyle{ \begin{cases} A(0)=6 \\ A(1)=21 \\ A(2)=11 \\ A(n>2) = 3* A(n-1) + A(n-3) + 10 * n + 2\end{cases}}\)
Należy wykazać, że dla całkowitego n \(\displaystyle{ \ge}\) 0 zachodzi A(n) \(\displaystyle{ \Leftrightarrow}\) 1 (mod 5).
Równanie rekurencyjne - jak rozwiązać
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Równanie rekurencyjne - jak rozwiązać
\(\displaystyle{ \begin{cases} A(0)=6 \equiv 1 \ (mod \ 5) \\ A(1)=21 \equiv 1 \ (mod \ 5) \\ A(2)=11 \equiv 1 \ (mod \ 5)\\ A(n>2) = 3 \cdot A(n-1) + A(n-3) + 10 \cdot n + 2 \equiv (3+1+0+2-5 ) \ (mod \ 5)= 1 \ (mod \ 5) \end{cases}}\)
Równanie rekurencyjne - jak rozwiązać
Dzięki za szybką odpowiedź, jednak jako że jestem dość zielony w temacie, to proszę o info, skąd wzięły się poszczególne współczynniki w rozwiązaniu tzn. fragment ( 3 + 1 + 0 + 2 -5)
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Równanie rekurencyjne - jak rozwiązać
Trzy początkowe wyrazy ciągu są \(\displaystyle{ 1 \ (mod \ 5)}\)
Każdy następny wyraz wylicza się z podanego wzoru rekurencyjnie. Więc zawsze dojdziemy do tego, że wcześniejsze elementy też są \(\displaystyle{ 1 \ (mod \ 5)}\), bo np:
\(\displaystyle{ A(3)= 3 \cdot A(2) + A(0) + 10 \cdot 3 + 2 \\ \\}\)
Wiemy, że:
\(\displaystyle{ A(2) \equiv 1 \ (mod \ 5) \Rightarrow 3 \cdot A(2) \equiv 3 \ (mod \ 5)\\
A(0) \equiv 1 \ (mod \ 5)\\
10 \cdot 3 \equiv 0 \ (mod \ 5)\\
2 \equiv 2 \ (mod \ 5)\\ \\
\Rightarrow A(3)\equiv (3+1+0+2-5) \ (mod \ 5)= 1 \ (mod \ 5)}\)
Odejmujemy 5, bo \(\displaystyle{ 3+1+0+2>5}\).
Czyli licząc kolejny element wiemy, że wszystkie poprzednie są \(\displaystyle{ \equiv 1 \ (mod \ 5)}\) i z tego wynika, że wszystkie \(\displaystyle{ A(n)\equiv 1 \ (mod \ 5)}\)
Każdy następny wyraz wylicza się z podanego wzoru rekurencyjnie. Więc zawsze dojdziemy do tego, że wcześniejsze elementy też są \(\displaystyle{ 1 \ (mod \ 5)}\), bo np:
\(\displaystyle{ A(3)= 3 \cdot A(2) + A(0) + 10 \cdot 3 + 2 \\ \\}\)
Wiemy, że:
\(\displaystyle{ A(2) \equiv 1 \ (mod \ 5) \Rightarrow 3 \cdot A(2) \equiv 3 \ (mod \ 5)\\
A(0) \equiv 1 \ (mod \ 5)\\
10 \cdot 3 \equiv 0 \ (mod \ 5)\\
2 \equiv 2 \ (mod \ 5)\\ \\
\Rightarrow A(3)\equiv (3+1+0+2-5) \ (mod \ 5)= 1 \ (mod \ 5)}\)
Odejmujemy 5, bo \(\displaystyle{ 3+1+0+2>5}\).
Czyli licząc kolejny element wiemy, że wszystkie poprzednie są \(\displaystyle{ \equiv 1 \ (mod \ 5)}\) i z tego wynika, że wszystkie \(\displaystyle{ A(n)\equiv 1 \ (mod \ 5)}\)