0

The proof I am working toward achieving is as follows:

enter image description here

I know this can be proven using induction, and in doing so, I will need to:

  • show when n = 2, F₂ = G₀; when n = 3, F₃ = G₁; if $F_{n -1} = G_{n - 3}$, then $F_n = G_{n - 2}$ for any $n > 2$
  • $G_{n - 3} = F_{n - 1}$; $G_{n - 4} = F_{n - 2}$; $G_{n - 2} = G_{n - 3} + G_{n - 4}$; $F_{n - 1} + F_{n - 2} = F_n$
  • $F_n = G_{n - 2}$ for all $n > 2$
genisage
  • 427
Jacob
  • 1
  • The question is weirdly-phrased; it might help to 'flip variables' and think of what you're trying to do as being to prove that (taking $k=n-2$ and reversing the equality) $G_k=F_{k+2}$ for all $k$. You already know the behavior of the sequence ${F_i}$, so you can treat it as a given; what you want to show is that your sequence ${G_i}$ is similar. – Steven Stadnicki Sep 15 '14 at 23:15
  • (And a broad sense as to how to do that: suppose the last character of a particular string (of length $n$) satisfying your condition is '$b$'; what does the rest of the string look like? Suppose instead that the last character of the string is '$a$'; what does the rest of the string look like then?) – Steven Stadnicki Sep 15 '14 at 23:16

1 Answers1

0

Let's just show that combinatorically,

Let $G_n$ be that number, let's look on a word that is legal first letter: - if it's an 'a' then the next letter must be 'b' and the remainder is a legal word with $n-2$ letters - $G_{n-2}$ - if it's a 'b' then the remainder is a legal word with length $n-1$ - $G_{n-1}$

Therefore $$G_n = G_{n-1} + G_{n-2}$$

With initial conditions: $G_0 = 1$ - the empty word is legal of length zero, and $G_1 = 2$, since all the words of length 2 are legal. Since $G_0 = F_2$ and $G_1 = F_3$ we get exactly what we want.

Snufsan
  • 2,125