Question 888109
How many different ways may a row of on-off switches be set if no two adjacent
switches may be off.
<pre>
Let 1 represent a switch that is on
Let 0 represent a switch that is off

A row of 1 switch can be set these and only these 2 ways:

1.  0
2.  1  

A row of 2 switches can be set these and only these 3 ways

1.  01
2.  10
3.  11

A row of 3 switches can be set these and only these 5 ways

1.  010
2.  011
3.  101
4.  110
5.  111

A row of 4 switches can be set these and only these 8 ways

1.  0101
2.  0110
3.  0111
4.  1010
5.  1011
6.  1101
7.  1110
8.  1111

Notice that this list of 4-switch settings consists 
of the 2-switch settings with a "<b><font color="red">10</font></b> annexed at the end

1.  01<b><font color="red">10</font></b>
2.  10<b><font color="red">10</font></b>
3.  11<b><font color="red">10</font></b>  

plus

the 3-switch setting with a 1 annexed at the end

1.  010<b><font color="red">1</font></b>
2.  011<b><font color="red">1</font></b>
3.  101<b><font color="red">1</font></b>
4.  110<b><font color="red">1</font></b>
5.  111<b><font color="red">1</font></b> 

This suggests the recursion formula:

{{{a[n+2]}}} {{{""=""}}} {{{a[n+1]}}}{{{""+""}}}{{{a[n]}}}

This is the Fibonacci recursion formula. 

If the Fibonacci numbers are considered as subscripted this way:

{{{F[1]=1}}}, {{{F[2]=1}}}, {{{F[3]=2}}}, {{{F[4]=3}}}, {{{F[5]=5}}}, {{{F[6]=8}}},{{{F[7]=13}}}, etc.

then if there are n switches, there are F<sub>n+2</sub> switch settings 
which have no two adjacent switches which are off.
</pre>
(b)2 How many numbers can be made from the digits 2,3,4,5,6 if they are to be
greater than 4000 and no repeats are allowed.
<pre>
This is easy compared to (a).

Case 1:  Four digit numbers:

Choose the first digit as any of these 3 digits: {4,5,6}.
Choose the second digit as any of the remaining 4 digits.
Choose the third digit as any of the remaining 3 digits.
Choose the fourth digit as either of the remaining 2 digits.

That's 3*4*3*2 = 72 ways

Case 2:  Five digit numbers:

Same as the four digit number.  Just tack the remaining 1 digit on
the right end of each of the 72 four digit numbers.

That's also 72 ways.

Anwer: 72+72 = 144 ways

Edwin</pre>