A sequence of positive integers with 2020 terms is called an $F T$ sequence if each term after the second is the sum of the previous two terms. For example, if the first two terms of an FT sequence are 8 and 7 , the sequence would begin $8,7,15,22,37, \ldots$ For some positive integer $m$, there are exactly 2415 FT sequences where the first two terms are each less than $2 m$ and the number of odd-valued terms is more than twice the number of even-valued terms. What is the value of $m$ ?
(A) 21
(B) 69
(C) 115
(D) 35
(E) 105
The property of an integer being either even or odd is called its parity.

If two integers are both even or they are both odd, then we say that the two integers have the same parity.

If one integer is even and a second integer is odd, then we say that the two integers have different parity.

The result of adding two integers that have the same parity is an even integer.

The result of adding two integers that have different parity is an odd integer.

The parity of each term of an FT sequence (after the second term) is determined by the parity of the first two terms in the sequence.

For example, if each of the first two terms of an FT sequence is odd, then the third term is even (since odd plus odd is even), the fourth term is odd (since odd plus even is odd), the fifth term is odd (since even plus odd is odd), and so on.

There are 4 possibilities for the parities of the first two terms of an FT sequence.

The sequence could begin odd, odd, or even, even, or odd, even, or even, odd.

In the table below, we write the parity of the first few terms of the FT sequences that begin in each of the 4 possible ways.

| Term Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| Parity $\# 1$ | odd | odd | even | odd | odd | even | odd | odd | even | odd |
| Parity $\# 2$ | even | even | even | even | even | even | even | even | even | even |
| Parity $\# 3$ | odd | even | odd | odd | even | odd | odd | even | odd | odd |
| Parity $\# 4$ | even | odd | odd | even | odd | odd | even | odd | odd | even |

The FT sequence beginning odd, odd (Parity \#1) continues to repeat odd, odd, even. Since the parity of each term is dependent on the parity of the two terms preceding it, this odd, odd, even pattern will continue throughout the entire sequence.

That is, in each successive group of three terms beginning at the first term, one out of three terms will be even and two out of three terms will be odd.

The odd, odd, even pattern ends at term numbers that are multiples of 3 (the even-valued terms are terms $3,6,9,12$, and so on).

Since 2019 is a multiple of $3(2019=3 \times 673)$, $\frac{1}{3}$ of the first 2019 terms will be even-valued and $\frac{2}{3}$ will be odd-valued, and so there are twice as many odd-valued terms as there are even-valued terms in the first 2019 terms.

The $2020^{\text {th }}$ term is odd (since the pattern begins with an odd-valued term), and so there are more than twice as many odd-valued terms as there are even-valued terms in every FT sequence that begins odd, odd.

This is exactly the required condition for the FT sequences that we are interested in.

How many FT sequences begin with two odd-valued terms, each of which is a positive integer less than $2 m$ ?

There are $2 m-1$ positive integers less than $2 m$ (these are $1,2,3,4, \ldots, 2 m-1$ ).

Since $m$ is a positive integer, $2 m$ is always an even integer and so $2 m-1$ is always odd.

Thus, the list of integers from 1 to $2 m-1$ begins and ends with an odd integer, and so the list contains $m$ odd integers and $m-1$ even integers.

The first term in the sequence is odd-valued and so there are $m$ choices for it.

Similarly, the second term in the sequence is also odd-valued and so there are also $m$ choices for it.

Thus, there are a total of $m \times m$ or $m^{2}$ FT sequences that begin with two odd-valued terms.

Do any of the other 3 types of FT seqences satisfy the required condition that there are more than twice as many odd-valued terms as there are even-valued terms?

Clearly the FT sequence beginning even, even (Parity \#2) does not satisfy the required condition since every term in the sequence is even-valued.

The FT sequence beginning odd, even (Parity \#3) continues to repeat odd, even, odd.

That is, in each successive group of three terms beginning at the first term, one out of three terms will be even and two out of three terms will be odd.

As we saw previously, 2019 is a multiple of 3 and so $\frac{1}{3}$ of the first 2019 terms are even-valued and $\frac{2}{3}$ are odd-valued.

Thus there are twice as many odd-valued terms as there are even-valued terms in the first 2019 terms.

The $2020^{\text {th }}$ term is odd (since the pattern begins with an odd-valued term), and so there are more than twice as many odd-valued terms as there are even-valued terms in every FT sequence that begins odd, even.

How many FT sequences begin with an odd-valued first term and an even-valued second term, each being a positive integer less than $2 m$ ?

As we showed previously, the list of integers from 1 to $2 m-1$ begins and ends with an oddvalued integer, and so the list contains $m$ odd-valued integers and $m-1$ even-valued integers. The first term in the sequence is odd-valued and so there are $m$ choices for it.

The second term in the sequence is even-valued and so there are $m-1$ choices for it.

Thus, there are a total of $m \times(m-1)$ FT sequences that begin with an odd-valued term followed by an even-valued term.

Finally, we consider the FT sequences that begin with an even-valued term followed by an odd-valued term (Parity \#4).

Again, there are exactly twice as many odd-valued terms as there are even-valued terms in the first 2019 terms (since the pattern repeats even, odd, odd).

However in this case, the $2020^{t h}$ term is even and so there are fewer than twice as many oddvalued terms as there are even-valued terms.

Thus, there are $m^{2}+m \times(m-1)$ FT sequences that satisfy the required conditions.

Since there are 2415 such FT sequences, we may solve $m^{2}+m \times(m-1)=2415$ by trial and error.

Evaluating $m^{2}+m \times(m-1)$ when $m=30$, we get $30^{2}+30 \times 29=1770$, and so $m$ is greater than 30 .

When $m=33$, we get $33^{2}+33 \times 32=2145$.

When $m=34$, we get $34^{2}+34 \times 33=2278$.

When $m=35$, we get $35^{2}+35 \times 34=2415$, as required.

ANSWER: (D)