1. ## recurrence relation

I notice that n must be even, thus we have
f(2)= 2
f(4)= 4
f(6)= 8
f(8)= 16

so every time we add a 3 by 2 grid , it doubled.

2. ## Re: recurrence relation

\displaystyle \begin{align*}f(0) & = 1 \\ f(1) & = 0 \\ f(2) & = 2 \\ f(3) & = 0 \\ f(4) & = 4 \\ f(5) & = 0 \\ f(6) & = 8 \\ f(7) & = 0 \\ f(8) & = 16\end{align*}

$\displaystyle \forall n\ge 0, f(n+2) = 2f(n)$

Note: The characteristic polynomial is $\displaystyle x^2-2$, so the roots are $\displaystyle \pm\sqrt{2}$. Hence $\displaystyle f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n$. Then $\displaystyle 1 = A+B$ and $\displaystyle 0 = A\sqrt{2} - B\sqrt{2}$, so solving the system of equations, we have $\displaystyle A = 1-B$ and $\displaystyle 0 = (1-2B)\sqrt{2}$, so $\displaystyle A = B = \dfrac{1}{2}$. Hence $\displaystyle f(n) = \dfrac{\left(\sqrt{2}\right)^n + \left(-\sqrt{2}\right)^n}{2}$

3. ## Re: recurrence relation

Originally Posted by SlipEternal
\displaystyle \begin{align*}f(0) & = 1 \\ f(1) & = 0 \\ f(2) & = 2 \\ f(3) & = 0 \\ f(4) & = 4 \\ f(5) & = 0 \\ f(6) & = 8 \\ f(7) & = 0 \\ f(8) & = 16\end{align*}

$\displaystyle \forall n\ge 0, f(n+2) = 2f(n)$

Note: The characteristic polynomial is $\displaystyle x^2-2$, so the roots are $\displaystyle \pm\sqrt{2}$. Hence $\displaystyle f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n$. Then $\displaystyle 1 = A+B$ and $\displaystyle 0 = A\sqrt{2} - B\sqrt{2}$, so solving the system of equations, we have $\displaystyle A = 1-B$ and $\displaystyle 0 = (1-2B)\sqrt{2}$, so $\displaystyle A = B = \dfrac{1}{2}$. Hence $\displaystyle f(n) = \dfrac{\left(\sqrt{2}\right)^n + \left(-\sqrt{2}\right)^n}{2}$
I notice that you answered my previous thread too and I'm really appreciated.However, your work seems beyond the method my professor have taught me or a completely different approach. For this one , everything just seems "MAGICAL" to me.

4. ## Re: recurrence relation

Given a recurrence relation of the form $\displaystyle f(n+k) = a_0 f(n) + a_1 f(n+1) + \ldots + a_{k-1}f(n+k-1)$, its characteristic polynomial is $\displaystyle x^k = a_0x^0 + a_1x^1 + \ldots + a_{k-1}x^{k-1}$. Let $\displaystyle \alpha_1, \ldots, \alpha_k$ be the roots of that characteristic polynomial. If the roots are all distinct, then $\displaystyle f(n) = \sum_{i = 1}^k A_i(\alpha_i)^n$. If the roots are not distinct, the formula is a bit more complex, and not necessary for this problem. The proof of this requires differential equations, but the process is frequently taught without proof in discrete mathematics classes.

To solve for $\displaystyle A_i$, you plug in the initial values $\displaystyle f(0) = \sum_{i = 1}^k A_i(\alpha_i)^0 = \sum_{i = 1}^k A_i$. $\displaystyle f(1) = \sum_{i = 1}^k A_i(\alpha_i)^1 = \sum_{i = 1}^k A_i\alpha_i$. Etc.

So, in this case, I used the characteristic polynomial to find $\displaystyle f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n$. Plugging in $\displaystyle f(0)=1=A(\sqrt{2})^0+B(-\sqrt{2})^0 = A+B$ and $\displaystyle f(1)=0=A(\sqrt{2})^1 + B(-\sqrt{2})^1 = (A-B)\sqrt{2}$. This gave me a system of two equations in two variables. I solved for $\displaystyle A$ and $\displaystyle B$, and plugged them in.