суми на Motzkin

Числовата редица суми на Motzkin (Motzkin sums, наричана още и числа на пръстена ring numbers съществува друга числова редица с името числа на пръстена, Riordan numbers) са цели числа,  представена е в http://oeis.org/A005043 с рекурентна формула: a(n) = (n-1)*(2*a(n-1)+3*a(n-2))/(n+1).

Съставете програма, чрез която се въвежда естествено число N от интервала [1..31] и се извеждат числа от редицата суми на Motzkin до указания номер. Програмата да използва две аналогични функции - рекурсия и итерация. Като използвате математическа индукция намерете докажете, че рекурентната формула a(n) = (n-1)*(2*a(n-1)+3*a(n-2))/(n+1) извежда същата числова редица.

Подробно описание за редица на Motzkin може да намерите на следните адреси: https://en.wikipedia.org/wiki/Motzkin_number. 

Разгледайте други основни типове примерни задачи, за чието решение се използват рекурсивни функции и рекурентни редици. Потърсете допълнителен материал за: числа на Motzkin, триъгълник на Motzkin.