Waste less time on Facebook — follow Brilliant.

Recurrence relation challenges

\(\textbf{Problem 1.}\)Each unit square of a \(2\)x\(n\) unit squae grid is to be colored blue or red such that no \(2\)x\(2\) red colored square is obtained.Let \(c_n\) denote the number of such colorings.Determine the greatest value of \(k\) such that \(3^{k} | c_{2001}\).

\(\textbf{Problem 2.}\)For any positive integer \(n\),p.t,the number of positive integers using only the digits \(1,3,4\) whose digit sum is \(2n\) is a perfect square.

\(\textbf{Problem 3.}\)A fair coin is tossed \(10\) times .What is the probability that heads never occur in consecutive tosses.

These problems are not original and are adapted from "A Path to Combinatorics for undergraduates" by Titu Andreescu and Zuming Feng.Post the solutions in the comments!!

Note by Eddie The Head
2 years, 5 months ago

No vote yet
1 vote


Sort by:

Top Newest

For the first one, I think the relation is such:

\(c_{n+1}=4c_n-c_{n-1}\), where \(c_0=1,c_1=4\).

Am I right? Bogdan Simeonov · 2 years, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...