Aufgabe:
Es sei \( x_{n} \) die Anzahl der Pfade mit \( n \) Schritten welche bei \( (0,0) \) beginnen, aus Schritten der Art \( O=(1,0), W=(-1,0) \) oder \( N=(0,1) \) bestehen und sich nie selbst überschneiden.
Bestimmen Sie die Anzahl derartiger Pfade mit \( n \) Schritten für alle \( n \in \mathbb{N}_{0} \).
Problem/Ansatz:
x_1=3
x_2=7
x_3=17
x_4=41
Wenn man sich das aufzeichnet, kann man immer an den Ecken immer entweder 3 oder 2 neue Pfade hinzufügen. Allerdings komme ich nicht so recht auf die richtige Formel. Ist es a_(n+1)=a_(n)*2+a_(n-1)? Aber ist x_0=1 überhaupt?
