Erzeugende Funktion für Folge gesucht. Rekursiv gilt a_n=2a_n-1+3a_n-2 mit a0=3 und a1=5 ( diskrete Mathe)

Question

Finden sie eine formel für die terme der durch die rekursion a_n=2a_n-1+3a_n-2 mit a₀=3 und a₁=5 gegebenen folge.

Answer 1

Ich habe zunächst die Glieder a₂ bis a₅ in Abhängigkeit von a₀ und a₁ dargestellt:

a₂ = 2 a₁+ 3 a₀

a₃ = 2 a₂ + 3 a₁ = 2 * ( 2 a₁ + 3 a₀ ) + 3 a₁ = 7 a₁ + 6 a₀

a₄ = 2 a₃ + 3 a₂ = 2 * ( 7 a₁ + 6 a₀ ) + 3 * ( 2 a₁+ 3 a₀ ) = 20 a₁ + 21 a₀

a₅ = 2 a₄ + 3 a₃ = 2 * ( 20 a₁ + 21 a₀ ) + 3 * ( 7 a₁ + 6 a₀ ) = 61 a₁ + 60 a₀

...

a_n = p_n a₁ + q_n a₀

Dann habe ich die Folge der rot gesetzten Koeffizienten p_n , also  2, 7, 20, 61 ...  von a₁ bei WolframAlpha eingegeben und den Hinweis auf die Folge OEIS A015518 erhalten:

http://oeis.org/A015518

Dort habe ich im Abschnitt "Mathematica" den Term

( 3 ⁿ - ( - 1 ) ⁿ ) / 4

gefunden, der die Koeffizienten p_n von 

a_n = p_n a₁ + q_n a₀

beschreibt (p_n = 2, 7, 20, 61 für n = 2, 3, 4, 5)

Schaut man sich nun noch die Folge der violett gesetzten Koeffizienten q_n, also 3, 6, 21, 60 ...  von a₀ an, so erkennt man, dass diese aus den Koeffizienten p_n durch Addition von ( - 1 ) ⁿ hervorgehen. Es gilt also offenbar:

q_n = p_n + ( - 1 ) ⁿ

Somit gilt für das Folgeglied a_n der rekursiv gegebenen Folge:

a_n = ( ( 3 ⁿ - ( - 1 ) ⁿ ) / 4 ) * a₁ + ( ( ( 3 ⁿ - ( - 1 ) ⁿ ) / 4 ) + ( - 1 ) ⁿ ) * a₀

= ( ( 3 ⁿ - ( - 1 ) ⁿ ) / 4 ) * ( a₁ + a₀ ) + ( - 1 ) ⁿ * a₀

Setzt man hier noch die Startwerte a₀ = 3 und a₁ = 5 ein, so erhält man:

a_n = ( ( 3 ⁿ - ( - 1 ) ⁿ ) / 4 ) * 8 + ( - 1 ) ⁿ * 3

= 2 * ( 3 ⁿ - ( - 1 ) ⁿ ) + ( - 1 ) ⁿ * 3

= 2 * 3 ⁿ - 2 * ( - 1 ) ⁿ + 3 * ( - 1 ) ⁿ

= 2 * 3 ⁿ + ( - 1 ) ⁿ

Comments

1. Somit gilt für das Folgeglied a_n

Ohne sauberen Induktionsbeweis bleibt das Spekulation

 

2. Die intendierte Lösungsmethode des Fragestellers (→ Überschrift) bleibt unerwähnt

---

Vorschlag: Nicht nur meckern, sondern besser machen!

---

Ich muss keine Eier legen können, um zu entscheiden, ob eins faul ist.

Die Methode "Erzeugende Funktion" läuft folgendermaßen ab :

Man betrachte die Potenzreihe  \( f(x) = \sum _{ n=0 }^{ \infty  }{ { a }_{ n }{ x }^{ n } } \) , in der die Koeffizienten \({ a }_{ n }\) durch die gegebene Folge geliefert werden mit noch zu bestimmendem Konvergenzradius. (Diese Funktion f wird als "erzeugende Funktion" bezeichnet.)

Ausklammern und Indexverschiebung führt zu 

\( f(x) = { a }_{ 0 }+{ a }_{ 1 }x+\sum _{ n=2 }^{ \infty  }{ { a }_{ n } } { x }^{ n } = { { a }_{ 0 }+{ a }_{ 1 }x+\sum _{ n=2 }^{ \infty  }{ (2{ a }_{ n-1 }+3{ a }_{ n-2 }) } { x }^{ n } = { { a }_{ 0 }+{ a }_{ 1 }x+2x\sum _{ n=2 }^{ \infty  }{ { a }_{ n-1 }{ x }^{ n-1 }+3{ { x }^{ 2 }\sum _{ n=2 }^{ \infty  }{ { a }_{ n-2 } }  } } { x }^{ n-2 } =  }{ a }_{ 0 } }+{ a }_{ 1 }x+2x(\sum _{ n=0 }^{ \infty  }{ { a }_{ n }{ x }^{ n }-{ a }_{ 0 })+3{ { x }^{ 2 }\sum _{ n=0 }^{ \infty  }{ { a }_{ n } }  } } { x }^{ n } \)

und also zu  f(x) = a₀+a₁x+2xf(x)-2a₀x+3x²f(x). Auflösen nach f(x) ergibt unter Berücksichtigung von  a₀=3 und a₁=5  den Bruch  f(x) = (3-x)  / (1-2x-3x²)  = 1/(1+x) + 2/(1-3x)  durch Partialbruchzerlegung.

Letzteres lässt sich für  |x| < 1/3  in geometrische Reihen entwickeln und liefert  \( f(x) = \sum _{ n=0 }^{ \infty  }{ { (-x) }^{ n }+2\cdot \sum _{ n=0 }^{ \infty  }{ { (3x) }^{ n } }  }  = \sum _{ n=0 }^{ \infty  }{ ({ (-1) }^{ n }+2\cdot { 3 }^{ n }) } { x }^{ n } \)  woraus sich durch Koeffizientenvergleich das von dir angegebene Resultat ergibt.

---

Ich muss keine Eier legen können, um zu entscheiden, ob eins faul ist.

Solch eine Entscheidung ist hier aber auch nicht gar nicht gefragt, sondern hier sollen gute Eier gelegt werden! :-)

Das ist dir mit deinem Kommentar aber auch hervorragend gelungen! Eine tolle Lösung!

Mir ist, ehrlich gesagt, diese Methode gar nicht bekannt. Deshalb habe ich sie nicht verwendet. Nun habe auch ich hier mal richtig was dazu gelernt!

Vorschlag: Mach doch diesen Kommentar zu einer Antwort  - wobei ich nicht weiß, ob das als Gast möglich ist .... ?