2
$\begingroup$

The the question is from the following problem:

Acceptable input for a certain pocket calculator is a finite sequence of characters each of which is either a digit or a sign. The first character must be a digit, the last character must be a digit, and any character that is a sign must be followed by a digit. There are 10 possible digits and 4 possible signs. If $N_k$ denotes the number of wuch acceptable sequences having length $k$, then $N_k$ is given recursively by

$A. \quad N_1=10, N_k=10N_{k-1}$
$B. \quad N_1=10, N_k=14N_{k-1}$
$C. \quad N_1=10, N_2=100, N_{k}=10N_{k-1}+40N_{k-2}$
$D. \quad N_1=10, N_2=140, N_k=14N_{k-1}+40N_{k-2}$
$E. \quad N_1=14, N_2=196, N_k=10N_{k-1}+14N_{k-2}$

It's not hard to rule out the wrong answers. But I don't see why the correct one is indeed correct. So here is my question:

Regardless of the choices, how can one deduce the recursive formula?

  • 0
    It's a joke. See also http:$/$/www.thinkgeek.com/tshirts-apparel/unise$x$/itdepartment/b2ae/2011-07-05

1 Answers 1

4

A valid string of length $k$ either begins with valid string of length $k-1$ ($10N_{k-1}$ term comes from this) or has the ($k-1$)th place filled with a sign,in which case the first $k-2$ symbols constitute a valid string of length $k-1$ (this gives $40N_{k-2}$ as there $4$ ways to choose the signs for $k-1$th place and $10$ ways to choose a digit for $k$th place)

  • 0
    Hmm. One can also understand it as $N_k=10(N_{k-1}+4N_{n-2})$.2011-07-06