-2
$\begingroup$

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$.

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.