Matematyka.pl

Cześć!

Mam pewien problem z pewnym dowodem. Chodzi o poniższą zależność rekurencyjną dla wielomianów Dicksona.
\(\displaystyle{ D_{n+2}(X,a)=XD_{n+1}(X,a)−aD_n(X,a) \ \text{for} \ n≥0 \ \text{z warunkami} \ D_0(X,a)=2 \ \text{and} \ D_1(X,a)=X}\).

Według źródła wynika to bardzo prosto z definicji tego wielomianu.
Niech \(\displaystyle{ \mathbb{K}}\) będzie ciałem, \(\displaystyle{ a \in \mathbb{K}}\). N-ty wielomian Dicksona definiujemy jako \(\displaystyle{ \begin{equation}
D_n(z+a/z,a)=z^n+(a/z)^n.
\end{equation}}\)
Możemy przyjąć, że \(\displaystyle{ x=z+a/z}\).
Niestety moje próby rozpisania tego się nie udają.

A próbowałeś indukcji zupełnej? To takie pierwsze co mi na myśl przychodzi. Imho wystarczy napaść:


przeliczyć, że wychodzi to co trzeba czyli \(\displaystyle{ z^{n+2}+ \frac{a^{n+2}}{z^{n+2}}}\) i powiedzieć \(\displaystyle{ \text{ZIM}}\), aby zaklęcie się dopełniło.

Ale czy Ty tutaj przypadkiem nie zakładasz tezy? Dlaczego wychodzisz z równości z tezy?

Nie zakładam tezy. To co robię to sprawdzenie założeń twierdzenia o indukcji zupełnej (lub silnej). Swoja drogą ten rodzaj indukcji jest równoważny ze zwykła indukcją więc nawet nie używam twierdzeń silniejszych od indukcji. Po wizualnym sprawdzeniu, że \(\displaystyle{ n=0}\) oraz \(\displaystyle{ n=1}\) działa. To znaczy wzór działa. Sprawdzam czy z założenia, że dla każdego \(\displaystyle{ n\in \NN}\) wzory na \(\displaystyle{ D_0,D_1,\dots,D_n}\) działają implikuje działanie wzoru na \(\displaystyle{ D_{n+1}}\). Okazuje się, że tak. Nie musiałem co prawda ciągnąć za sobą ogona \(\displaystyle{ n+1}\) działających wzorów na \(\displaystyle{ D_0,D_1,\dots,D_n}\) bo wystarczą mi jedynie dwa ostatnie \(\displaystyle{ D_0,D_1,\dots,\red{D_{n-1},D_n}}\) by napisać \(\displaystyle{ D_{n+1}(X,a)=XD_{n}(X,a)−aD_{n-1}(X,a)}\) i dostać to co trzeba (czyli wzór na \(\displaystyle{ D_{n+1}}\) postulowany przez tezę). A to, że napisałem wzór na \(\displaystyle{ D_{n+2}}\) nie ma nic do rzeczy bo to tylko przesunięcie.

Rozumowanie powinno wyglądać tak: z definicji \(\displaystyle{ D_n(X, a)}\) jest (jedynym) wielomianem, takim że zachodzi równość funkcji wymiernych zmiennej \(\displaystyle{ z}\)

\(\displaystyle{ D_n\left( z+\frac{a}{z}, a \right) = z^n + \left( \frac{a}{z} \right)^n}\).

Sprawdzamy ręcznie, że wielomiany \(\displaystyle{ 2}\) i \(\displaystyle{ X}\) spełniają równość dla \(\displaystyle{ n=0}\) i \(\displaystyle{ n=1}\), zatem muszą się równać \(\displaystyle{ D_0(X, a)}\) i \(\displaystyle{ D_1(X, a)}\), odpowiednio. Dla \(\displaystyle{ n \ge 2}\) używając równości (wynikających z definicji)

\(\displaystyle{ D_{n-2}\left( z+\frac{a}{z}, a \right) = z^{n-2} + \left( \frac{a}{z} \right)^{n-2} \\[1ex]
D_{n-1}\left( z+\frac{a}{z}, a \right) = z^{n-1} + \left( \frac{a}{z} \right)^{n-1}}\)

sprawdzamy, że wielomian dany wzorem

\(\displaystyle{ F(X) = X D_{n-1}(X, a) - a D_{n-2}(X, a)}\)

spełnia zależność

\(\displaystyle{ F\left( z+\frac{a}{z}, a \right) = z^n + \left( \frac{a}{z} \right)^n}\),

a zatem z definicji \(\displaystyle{ D_n(X, a) = F(X)}\), co kończy dowód. Nawiasem mówiąc, dowód nieindukcyjny.

Dasio11 pisze: ↑16 lis 2022, o 12:08 Rozumowanie powinno wyglądać tak:...

Czyli to moje jest źle?

Prawdopodobnie tak, bo Twoja propozycja sprawia wrażenie, jakbyś pomylił założenie z tezą. Ale trudno to jednoznacznie stwierdzić, bo podajesz za mało konkretów.

Janusz Tracz pisze: ↑16 lis 2022, o 10:59Sprawdzam czy z założenia, że dla każdego \(\displaystyle{ n\in \NN}\) wzory na \(\displaystyle{ D_0,D_1,\dots,D_n}\) działają implikuje działanie wzoru na \(\displaystyle{ D_{n+1}}\).

Które wzory?

Janusz Tracz pisze: ↑16 lis 2022, o 10:59napisać \(\displaystyle{ D_{n+1}(X,a)=XD_{n}(X,a)−aD_{n-1}(X,a)}\) i dostać to co trzeba (czyli wzór na \(\displaystyle{ D_{n+1}}\) postulowany przez tezę).

Czy "napisać" znaczy "wykorzystać założenie", czy "wykazać"? Który wzór jest postulowany przez tezę?

Poza tym raczej nie sądzę, żeby w tym zadaniu dało się z sensem wykorzystać indukcję.

Dasio11 pisze: ↑16 lis 2022, o 15:07 Prawdopodobnie tak, bo Twoja propozycja sprawia wrażenie, jakbyś pomylił założenie z tezą.

Chwila... czyli, że to my tej zależności rekurencyjnej mamy dowieść? Ja dowodziłem, że z rekurencji wynika jawny wzór \(\displaystyle{ D_n\left( z+\frac{a}{z}, a \right) = z^n + \left( \frac{a}{z} \right)^n}\). Ale jak teraz czytam to pytanie pawlo392 no to faktycznie. Zwykle najpierw podaje się pojawia założenie, a potem to czego dowodzimy (chyba). Sorki w taki razie No cóż masz dowód równoważności.