I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21.
i see the result is:
$a_n=15a_{n-2}+7a_{n-1}$
How this was calculated? any hint or idea highly appreciated.
Letting $\alpha\lt \beta$ be the roots of $$x^2-15x-7=0,$$ we have $$a_{n+1}-\alpha a_n=\beta(a_n-\alpha a_{n-1})=\cdots=\beta^n(a_1-\alpha a_0),$$ $$a_{n+1}-\beta a_n=\alpha(a_n-\beta a_{n-1})=\cdots=\alpha^n(a_1-\beta a_0).$$ Subtracting the latter from the former gives us $$(\beta-\alpha)a_n=\beta^n(a_1-\alpha a_0)-\alpha^n(a_1-\beta a_0)$$ i.e. $$a_n=\frac{\beta^n(a_1-\alpha a_0)-\alpha^n(a_1-\beta a_0)}{\beta-\alpha}$$ where $$\alpha=\frac{15-\sqrt{253}}{2},\ \ \ \beta=\frac{15+\sqrt{253}}{2}.$$
P.S. By Vieta's formulas, we have $$\alpha+\beta=-\frac{-15}{1}=15,\ \ \ \alpha\beta=\frac{-7}{1}=-7.$$ Hence, you'll see that $$a_{n+1}-\alpha a_n=\beta(a_n-\alpha a_{n-1})$$ $$a_{n+1}-\beta a_n=\alpha(a_n-\beta a_{n-1})$$ are the same as $$a_{n+1}=15a_n+7a_{n-1}.$$