Liniowa zależność rekurencyjna.

[pawlo392]

Mamy następujący zbiór : \(\displaystyle{ \left\{ 1,2,....,k\right\}}\). Niech \(\displaystyle{ a_k}\) oznacza liczbę podzbiorów niepustych w/w zbioru, które nie zawierają dwóch kolejnych liczb. Jak będzie wyglądać liniowa zależność rekurencyjna na \(\displaystyle{ b_k}\) ?

[leg14]

myśl o elementach z \(\displaystyle{ a_{k+1}}\) jako o zbiorach powstających z \(\displaystyle{ a_k,a_{k-1}}\) przez operację dodania \(\displaystyle{ k+1}\) lub brak jakichkolwiek zmian. Np. weź \(\displaystyle{ w \in a_{k+1}}\), który nie ma \(\displaystyle{ k+1}\) - jasne jest, że takie \(\displaystyle{ w}\) wyznacza jednoznacznie pewne \(\displaystyle{ w' \in a_k}\)

[arek1357]

Wzór będzie prosty a nawet jawny:

dla:

\(\displaystyle{ \left\{ 1,2,3,...,k\right\}}\)

będziesz miał coś takiego:

1). dla k parzystych:

\(\displaystyle{ k+(1+2+...+k-2)+(1+2+...+k-4)+...+(1+2)}\)


2). dla k nieparzystych:

\(\displaystyle{ k+(1+2+...+k-2)+(1+2+...+k-4)+...+(1+2+3)+(1)}\)

łatwo to wszystko pozwijać i można mieć wzór jawny, rekurencyjny jaki chcesz...