Let an 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 bn = the number of such n-digit integers ending with digit 1 and cn = the number of such n-digit integers ending with digit 0. Which of the following is correct?

In such a number either last digit is′0′or′1′When you consider′a′1, only one number is possible i.e.1When you consider′a′2, 2 such numbers are possible i.e.10,11When you consider′a′3, 3 such numbers are possible i.e.101,111,110When you consider′a′4, 5 such numbers are possible i.e.1010,1011,1110,1101,1111By observing this we get a relationship which isan=an𕒵+an𕒶So,a17=a16+a15(Alternate Method)Using Recursion formulaan=an𕒵+an𕒶Similarly,bn=bn𕒵+bn𕒶andcn=cn𕒵+cn𕒶∀ n≥3andan=bn+cn∀ n≥1So,a1=1,a2=2,a3=3,a4=5,a5=8...b1=1,b2=1,b3=2,b4=3,b5=5,b6=8...c1=0,c2=1,c3=1,c4=2,c5=3,c6=5...Using this we getbn𕒵=cn∴a17=a16+a15