Create the page "Linear recursion" on this wiki! See also the search results found.

• Fibonacci sequence
  ==Recursion== ...th>n \geq 3</math>. This is the simplest nontrivial example of a [[linear recursion]] with constant coefficients. There is also an explicit formula [[#Binet's
  7 KB (1,111 words) - 14:57, 24 June 2024
• 1985 AIME Problems/Problem 12
  == Solution 1 (Single Variable Recursion) == == Solution 2 (Multivariable Recursion by Algebra) ==
  19 KB (3,128 words) - 21:38, 23 July 2024
• 1988 AIME Problems/Problem 13
  The above uses the similarity between the Fibonacci recursion|recursive definition, <math>F_{n+2} - F_{n+1} - F_n = 0</math>, and the pol We rewrite the left side of <math>(\bigstar)</math> as a linear expression of <math>r:</math>
  10 KB (1,595 words) - 16:30, 24 August 2024
• 1989 AIME Problems/Problem 8
  ...ath>f(k)=ak^2+bk+c,</cmath> where <math>a,b,</math> and <math>c</math> are linear combinations of <math>x_1,x_2,x_3,x_4,x_5,x_6,</math> and <math>x_7.</math> == Solution 2 (Linear Combination) ==
  9 KB (1,312 words) - 12:10, 15 December 2024
• 2003 AIME II Problems/Problem 13
  ...ill be extremely lengthy because I am assuming just very basic concepts of linear algebra. The concepts here extend to higher levels of mathematics, so feel ...st assess the kernel of this matrix (also known as the null space), or the linear subspace of the domain of <math>\hat{T}</math> where everything gets mapped
  15 KB (2,406 words) - 23:56, 23 November 2023
• 2007 AIME I Problems/Problem 14
  ...all <math>n\ge 1</math>. To do this, we use the following matrix form of a linear recurrence relation ...r all <math>n\ge 1</math>. We conclude that <math>a_n</math> satisfies the linear recurrence <math>a_{n+1}=225a_n-a_{n-1}</math>.
  13 KB (2,214 words) - 17:39, 28 November 2024
• Binet's Formula
  ==Proof using Recursion== ...on is <math>F_n = F_{n-1} + F_{n-2}.</math> This is a constant coefficient linear homogenous recurrence relation. We also know that <math>F_0 = 0</math> and
  6 KB (955 words) - 02:11, 5 February 2025
• Characteristic polynomial
  The '''characteristic polynomial''' of a linear [[operator]] refers to the [[polynomial]] whose roots are the [[eigenvalue] ...often used to find closed forms for the solutions of [[#Linear recurrences|linear recurrences]].
  19 KB (3,412 words) - 14:57, 21 September 2022
• 2010 IMO Problems/Problem 6
  :<math>\text{Our plan is to view each } a_{n} \text{ as a linear combination of the weights } w_{1}\text{, ..., } w_{s} \text{ and track the ...text{the linear combinations possible in the recursion, in other words the recursion in the problem is phrased as}</math>
  4 KB (786 words) - 08:46, 12 March 2024
• 2016 AMC 12B Problems/Problem 25
  .../math> for all <math>n\geq 2</math>. The characteristic polynomial of this linear recurrence is <math>x^2-x-2=0</math>, which has roots <math>2</math> and <m ...h>. Using the fact that <math>b_0=0, b_1=1,</math> we can solve a pair of linear equations for <math>k_1, k_2</math>:
  5 KB (956 words) - 00:43, 10 November 2024
• 2018 AMC 10B Problems/Problem 20
  ...In the case in which finite differences didn’t reduce to such a special recursion, you could still find the first few terms of <math>C</math> to see if there ...ath>n=3</math>, and <math>n=4</math> results in a system of <math>4</math> linear equations<math>\newline</math>
  10 KB (1,578 words) - 06:18, 15 December 2024
• 2018 AIME II Problems/Problem 13
  ...ast three rolls are <math>123</math> for the game to end. Summing over the recursion, we obtain ...= 1-P_o</math> and <math>P_e(1) = 1 - P_o(1)</math>, we have a 3-equation linear system which is not hard to solve. The final answer is <math>Po=\frac{216}{
  11 KB (1,860 words) - 13:12, 24 January 2024
• Newton's method
  ...possible roots is found, and in some cases the initial guess can cause the recursion to cycle or diverge instead of converging to a root. ...seek a root of <math>f(x)</math>. Since all nonconstant [[Linear function|linear functions]] have exactly one root, as long as <math>f'(x_i) \neq 0</math> w
  13 KB (2,298 words) - 23:34, 28 May 2023
• Secant method
  ...th> The values <math>x_0</math> and <math>x_1</math> used initially in the recursion are guesses. ...s <math>(x_{i-1}, f(x_{i-1}))</math> and <math>(x_i, f(x_i))</math> is a [[linear function]], it has exactly one root (unless <math>f(x_{i-1}) = f(x_i)</math
  2 KB (337 words) - 15:30, 9 May 2022
• 2022 AMC 12B Problems/Problem 11
  == Solution 4 (Third-order Homogeneous Linear Recurrence Relation) == == Solution 5 (Polynomial + Recursion) ==
  5 KB (886 words) - 23:57, 1 November 2024
• 2023 AIME I Problems/Problem 6
  ...r of remaining unrevealed cards of each color. Since [[expected value]] is linear, the expected value of the total number of correct card color guesses acros ==Solution 5 (Pseudo-recursion)==
  13 KB (2,015 words) - 05:23, 5 February 2025
• Problems Collection
  Now, you can bash through solving linear congruences, but there is a smarter way. Notice that <math>5|x-6,6|x-6</mat ===Solution 1 (Recursion)===
  64 KB (10,614 words) - 21:48, 26 April 2025
• Number Theory Problems Collection
  Now, you can bash through solving linear congruences, but there is a smarter way. Notice that <math>5|x-6,6|x-6</mat ...> that can transfer <math>n</math> rings onto the second peg. To build the recursion, we consider what is the minimum possible number <math>moves</math> that ca
  25 KB (4,018 words) - 21:21, 19 March 2025