Question

# Let $$a_{n}$$ denote the number of all n-digit positive integers formed by the digits $$0,1$$ or both such thatÂ no consecutive digits in them are $$0$$. Let $$b_{n}=$$ the number of such $$n$$-digit integers ending with digit $$1$$ and $$c_{n}=$$ the number of such $$n$$-digit integers ending with digit $$0$$.Â Which of the following is correct?

A
a17=a16+a15
B
c17c16+c15
C
b17b16+c16
D
a17=c17+b16

Solution

## The correct option is A $$a_{17}=a_{16}+a_{15}$$In such a number either last digit is $$'0'$$ or $$'1'$$When you consider $$'a_1'$$, only one number is possible i.e. $$1$$When you consider $$'a_2'$$, 2 such numbers are possible i.e. $$10$$, $$11$$When you consider $$'a_3'$$, 3 such numbers are possible i.e. $$101$$, $$111$$, $$110$$When you consider $$'a_4'$$, 5 such numbers are possible i.e. $$1010$$, $$1011$$, $$1110$$, $$1101$$, $$1111$$By observing this we get a relationship which is $$a_n$$ $$=$$ $$a_{n-1}$$ $$+$$ $$a_{n-2}$$So, $$a_{17}$$ $$=$$ $$a_{16}$$ $$+$$ $$a_{15}$$(Alternate Method)Using Recursion formula$$a_n=a_{n-1}+a_{n-2}$$Similarly, $$b_n=b_{n-1}+b_{n-2}$$ and $$c_n=c_{n-1}+c_{n-2}$$    $$\forall\ n\geq 3$$and $$a_n=b_n+c_n$$  $$\forall\ n\geq 1$$So, $$a_1=1, a_2=2, a_3=3, a_4=5, a_5=8$$ .......$$b_1=1, b_2=1, b_3=2, b_4=3, b_5=5, b_6=8$$ .......$$c_1=0, c_2=1, c_3=1, c_4=2, c_5=3, c_6=5$$ .......Using this we get $$b_{n-1}=c_n$$$$\therefore a_{17}=a_{16}+a_{15}$$Mathematics

Suggest Corrections
Â
0

Similar questions
View More

People also searched for
View More