×

# 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!!

2 years, 5 months ago

Sort by:

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? · 2 years, 5 months ago