Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 1988 based on Fibonacci sequence.

Fibonacci sequence Problem – AIME I, 1988


Find a if a and b are integers such that \(x^{2}-x-1\) is a factor of \(ax^{17}+bx^{16}+1\).

  • is 107
  • is 987
  • is 840
  • cannot be determined from the given information

Key Concepts


Integers

Digits

Sets

Check the Answer


But try the problem first…

Answer: is 987.

Source
Suggested Reading

AIME I, 1988, Question 13

Elementary Number Theory by David Burton

Try with Hints


First hint

Let F(x)=\(ax^{17}+bx^{16}+1\)

Let P(x) be polynomial such that

\(P(x)(x^{2}-x-1)=F(x)\)

constant term of P(x) =(-1)

now \((x^{2}-x-1)(c_1x^{15}+c_2x^{14}+….+c_{15}x-1)\) where \(c_{i}\)=coefficient

Second Hint

comparing the coefficients of x we get the terms

since F(x) has no x term, then \(c_{15}\)=1

getting \(c_{14}\)

\((x^{2}-x-1)(c_1x^{15}+c_2x^{14}+….+c_{15}x-1)\)

=terms +\(0x^{2}\) +terms

or, \(c_{14}=-2\)

proceeding in the same way \(c_{13}=3\), \(c_{12}=-5\), \(c_{11}=8\) gives a pattern of Fibonacci sequence

Final Step

or, coefficients of P(x) are Fibonacci sequence with alternating signs

or, a=\(c_1=F_{16}\) where \(F_{16}\) is 16th Fibonacci number

or, a=987.

Subscribe to Cheenta at Youtube