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

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.\phantom{\rule{1em}{0ex}}{N}_{1}=10,{N}_{k}=10{N}_{k-1}$
$B.\phantom{\rule{1em}{0ex}}{N}_{1}=10,{N}_{k}=14{N}_{k-1}$
$C.\phantom{\rule{1em}{0ex}}{N}_{1}=10,{N}_{2}=100,{N}_{k}=10{N}_{k-1}+40{N}_{k-2}$
$D.\phantom{\rule{1em}{0ex}}{N}_{1}=10,{N}_{2}=140,{N}_{k}=14{N}_{k-1}+40{N}_{k-2}$
$E.\phantom{\rule{1em}{0ex}}{N}_{1}=14,{N}_{2}=196,{N}_{k}=10{N}_{k-1}+14{N}_{k-2}$
Regardless of the choices, how can one deduce the recursive formula?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

A valid string of length $k-1$ either begins with valid string of length $k-1$ ($10{N}_{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 $40{N}_{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)