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

4 years, 4 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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?

- 4 years, 4 months ago