$n$ strips are to be coloured using three colours viz. red, blue and green. In how many ways can they be coloured so that no two consecutive strips are of same colour?
My Attempt:
Let $a_n$ be the number of ways to paint the strips in manner specified.
Consider the colouring of $(n+1)$st strip:
If we colour the first $n$ strips in $a_n$ ways , then the (n+1)th strip can be coloured in $2$ ways.So the number of ways to paint the $n+1$ strips will be $2a_n$.
What could be the other possibility?
Best Answer
Let's prove that the ways of coloring $n$ strips is equal to $a_n = 3\cdot2^{n-1}$ by induction:
Base case: $n=1$
There are $3$ ways to color $1$ strip, $a_1 = 3 = 3\cdot2^{1-1}$
Inductive step:
Given that there are $a_k = 3\cdot2^{k-1}$ ways to color $k$ strips, let's prove $a_{k+1} = 3\cdot2^{k}$ After coloring $k$ strips, as you said in your question, we have $2$ ways to color the $(k+1)$th which gives a total of $2a_k = 3\cdot2^{k}$ ways to color $k+1$ strips.
Conclusion: Because both the base step and inductive step was proved, the number of ways of coloring $n$ strips, $a_n = 3\cdot2^{n-1}$