retagged by
628 views
7 votes
7 votes
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 such acceptable sequences having length $k$, then $N_k$ is given recursively by

$N_k=a N _{k-1}+b N _{k-2}$, for $k \geq 3$.

What is $a+ b?$
retagged by

2 Answers

7 votes
7 votes

N1 = 10, As for 1 length string it can be only digit so 10 strings possible

N2 = 100, Again as the string has to start and end with digits so 10*10 strings possible

We would have to find N3 and N4 and then need to compute a and b by solving equation

N3 = 10*4*10  (because starts and ends with digit so 10 choices and in between 4 choice of operators) + 10*10*10 (all three digits) = 1400

Similarly

N4 = 10*4*10*10 + 10*10*4*10 + 10*10*10*10 = 18000

so we get two equation,

1400 = 100a + 10b [ N2 = 100, N1 = 10]                                     – eq 1

18000 = 1400a + 100b [N3 = 1400, N2 = 100]                            -eq 2

Solving the above Linear Equation;

Multiplying eq 1 with 14 on both sides

19600 = 1400a + 140b

18000 = 1400a + 100b                -eq2

=> 1600 = 40b

=> b = 40

And from eq1 e can get a = 10.

Hence, a + b = 50

 

edited by
3 votes
3 votes
We know that if the first character must be a digit and the last a digit, that gives $N_1 = 10$ and $N_2 = 100.$
$$
\begin{aligned}
& N_1=10 \\
& N_2=100 \\
& N_k=10 N_{k-1}+40 N_{k-2}
\end{aligned}
$$
edited by
Answer:

Related questions

647
views
1 answers
5 votes
GO Classes asked Jan 13
647 views
Consider the following $6 \;\mathrm{I} / \mathrm{O}$ operations and their respective cylinder locations on disk. Seek time is $0.1$ milliseconds per cylinder traversed. The ... $10 \ast(\mathrm{X}-\mathrm{Y})?$
507
views
1 answers
5 votes
GO Classes asked Jan 13
507 views
The following table lists the arrival time and execution time of $5$ ... starts at zero, what is the time at which $\mathrm{E}$ finishes its execution?
509
views
1 answers
6 votes
GO Classes asked Jan 13
509 views
Consider the following pair of mutually recursive functions. What does $g(g(2))$ evaluate to?int f(int n){ if (n==0) return 0; return f(n-1)+g(n-1); } int g(int n){ if (n==0) return 1; return g(n-1) + f(n); }
689
views
1 answers
5 votes
GO Classes asked Jan 13
689 views
Host A has to inject' $30$ Mbits of data into a network via a token bucket regulator. The token bucket has a capacity of $15$ Mbits and is filled with ... host sends at a peak rate of $20$ Mbps and the token bucket is initially full?