Задача
ALG-B1-M10-P019 Линейная рекурсия
#19
★★★★☆ Уровень 4 из 5
Пусть \(u_0=1\), \(u_1=3\), \(u_{n+2}=3u_{n+1}-2u_n\). Докажите, что \(u_n=2^{n+1}-1\).
Проверьте базу и сделайте индукционный переход.
Для \(n=0,1\) формула верна. Если \(u_n=2^{n+1}-1\) и \(u_{n+1}=2^{n+2}-1\), то \(u_{n+2}=3(2^{n+2}-1)-2(2^{n+1}-1)=2^{n+3}-1\). Формула доказана.
Рекурсия среди задач других типов проверяет распознавание.