ciąg rekurencyjny

[ann_u]

Niech \(\displaystyle{ a_1=1, a_n=(n-1)a_{n-1}+1,n\ge 2}\). Znaleźć wszystkie n takie że \(\displaystyle{ n|a_n.}\)

[arek1357]

Łatwo w tym ciągu wyszukać jawny wzór węsząc...

Jest to ciąg bardzo mocno związany z funkcją Gamma...
I z liczbą \(\displaystyle{ e}\)

\(\displaystyle{ a_{n}=(n-1)!\left( 2+ \frac{1}{2!}+ \frac{1}{3!}+...+ \frac{1}{(n-1)!} \right) }\)

lub:

\(\displaystyle{ a_{n}=2(n-1)!+ \frac{(n-1)!}{2!}+ \frac{(n-1)!}{3!}+...+ \frac{(n-1)!}{(n-1)!} }\)

Rozpiszmy to jeszcze inaczej:


\(\displaystyle{ a_{n}=2(n-1)!+1+n-1+(n-2)(n-1)+(n-3)(n-2)(n-1)+...+(n-1)(n-2) \cdot ... \cdot 3}\)

\(\displaystyle{ a_{n}=2(n-1)!+n+(n-2)(n-1)+(n-3)(n-2)(n-1)+...+(n-1)(n-2) \cdot ... \cdot 3}\)

teraz zróbmy:

\(\displaystyle{ a_{n} \mod n=2(n-1)! +2!-3!+4!+...+(-1)^{n-3}(n-3)!=0}\) - kiedy?

I teraz widać,że jeżeli ta suma modulowo wyjdzie zero to mamy, że:

\(\displaystyle{ n|a_{n}}\)

Nie jest to zbyt piękny wzór i warunek na podzielność ale trudno go bardziej skrócić, troszkę inaczej jest dla \(\displaystyle{ n}\) pierwszych a inaczej dla złożonych gdzie silnie od pewnej silni się już zerują...

Bo wystąpią dzielniki zera w nadmiarze...