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?

-
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

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)
Hmm. One can also understand it as $N_k=10(N_{k-1}+4N_{n-2})$. – Jack Jul 6 '11 at 16:08