Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
Unfortunately, you cannot understand recursion unless you first understand recursion. –  Gerry Myerson Jun 29 '11 at 6:49
@Gerry: I am not able to catch up with you. –  Jack Jul 5 '11 at 2:34
It's a joke. See also thinkgeek.com/tshirts-apparel/unisex/itdepartment/b2ae –  Gerry Myerson Jul 5 '11 at 4:21

1 Answer 1

up vote 4 down vote accepted

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)

share|improve this answer
Hmm. One can also understand it as $N_k=10(N_{k-1}+4N_{n-2})$. –  Jack Jul 6 '11 at 16:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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