# Let Sn be the set of all natural numbers in the decimal system consisting of n digits such that no successive digits of this number is zero.

Let $S_n$ be the set of all natural numbers in the decimal system consisting of n digits such that no successive digits of this number is zero.

Let $A_n$ be the number of elements in $S_n$

Then define natural numbers $x,y$ by $$A_9=xA_8+yA_7$$

Find out the square root of $xy$.

• Hint: a "good" number either ends in $X$ or $X0$ where $X$ denotes a non-zero digit. – lulu Dec 31 '17 at 14:26

The idea of the following argument is the same as the one suggested in lulu's hint, except I chose to start on the left . . .

Fix $n > 2$, and let $s \in S_n$.

Let the digit representation of $s$ be $d_1d_2\cdots d_n$ (left-to-right).

The leading digit of $s$ can be any digit except $0$, hence there are $9$ choices for $d_1$.

Consider two cases . . .

Case $(1)$:$\;d_2 \ne 0$.

Then the $(n-1)$-digit number with digit representation $d_2\cdots d_n$ can be any element of $S_{n-1}$, so for case $(1)$, there are $9A_{n-1}$ possibilities for $s$.

Case $(2)$:$\;d_2 = 0$.

Then the $(n-2)$-digit number with digit representation $d_3\cdots d_n$ can be any element of $S_{n-2}$, so for case $(2)$, there are $9A_{n-2}$ possibilities for $s$.

Summing up the counts for the two cases, we get $A_{n} = 9A_{n-1} + 9A_{n-2}$, for all $n > 2$.

So presumably, $x=9$ and $y=9$ are the intended values of $x,y$.

• So not sure?/// – starunique2016 Dec 31 '17 at 20:53
• $x=9$ and $y=9$ are surely the intended values of $x,y$ (i.e., the recursion is correct). – quasi Dec 31 '17 at 21:01
• but presumedly? – starunique2016 Dec 31 '17 at 21:02
• If there's only one answer, then $x=9$ ans $y=9$ will give that answer. – quasi Dec 31 '17 at 21:03