TITLE: question about counting recursively
QUESTION [2 upvotes]: 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?

REPLY [3 votes]: 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)
{"set_name": "stack_exchange", "score": 2, "question_id": 48325}