Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n .
Memecahkan relasi perulangan berarti memperoleh solusi bentuk tertutup: fungsi non-rekursif dari n .
More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form u nφ ( n , u n − 1 ) for n > 0 ,\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,} where φ : N × X → X \times X\to X} is a function, where X is a set to which the elements of a sequence must belong.
Lebih tepatnya, dalam kasus di mana hanya elemen sebelumnya yang terlibat, relasi perulangan memiliki bentuk u nφ ( n , u n − 1 ) untuk n > 0 ,\varphi (n,u_{n-1})\quad {\text{untuk}}\quad n>0,} di mana φ : N × X → X \times X\to X} adalah sebuah fungsi, di mana X adalah himpunan yang harus dimiliki elemen-elemen urutan.
For any u 0 ∈ X \in X} , this defines a unique sequence with u 0 } as its first element, called the initial value.
Untuk apapun u 0 ∈ X \in X} , ini mendefinisikan urutan unik dengan u 0 } sebagai elemen pertamanya, yang disebut nilai awal.
It is easy to modify the definition for getting sequences starting from the term of index 1 or higher.
Sangat mudah untuk mengubah definisi untuk mendapatkan urutan mulai dari indeks 1 atau lebih tinggi.
A recurrence relation of order k has the form u nφ ( n , u n − 1 , u n − 2 , … , u n − k ) for n ≥ k ,\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,} where φ : N × X k → X \times X^{k}\to X} is a function that involves k consecutive elements of the sequence.
Relasi perulangan orde k memiliki bentuk u nφ ( n , u n − 1 , u n − 2 , … , u n − k ) for n ≥ k ,\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,} di mana φ : N × X k → X \times X^{k}\to X} adalah fungsi yang melibatkan k elemen berurutan dari urutan tersebut.
for n > 0 , }\quad n>0,} and the initial condition 0 !
n ( n − 1 ) ! untuk n > 0 , }\quad n>0,} dan kondisi awal 0 !
The Fibonacci sequence is defined using the recurrence F nF n − 1 + F n − 2F_{n-1}+F_{n-2}} with initial conditions F 000} F 11.1.}
Urutan Fibonacci ditentukan menggunakan pengulangan F nF n − 1 + F n − 2F_{n-1}+F_{n-2}} dengan kondisi awal (nilai benih)
Explicitly, the recurrence yields the equations F 2F 1 + F 0F_{1}+F_{0}} F 3F 2 + F 1F_{2}+F_{1}} F 4F 3 + F 2F_{3}+F_{2}} etc.
F 000} F 11.1.} Secara eksplisit, pengulangan menghasilkan persamaan F 2F 1 + F 0F_{1}+F_{0}} F 3F 2 + F 1F_{2}+F_{1}} F 4F 3 + F 2F_{3}+F_{2}} etc.
{1-t-t^{2}}}.} A simple example of a multidimensional recurrence relation is given by the binomial coefficients ( n k ) {k}}} , which count the ways of selecting k elements out of a set of n elements.
{1-t-t^{2}}}.} Contoh sederhana dari relasi perulangan multidimensi diberikan oleh koefisien binomial ( n k ) {k}}} , yang menghitung jumlah cara memilih elemen k dari satu set elemen n .
( n − 1 k − 1 ) + ( n − 1 k ) , {k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},} with the base cases ( n 0 )( n n )1 {0}}={\tbinom {n}{n}}=1} .
( n − 1 k − 1 ) + ( n − 1 k ) , {k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},} dengan kasus dasar ( n 0 )( n n )1 {0}}={\tbinom {n}{n}}=1} .
The parentheses around Δ f and Δ a are generally omitted, and Δ a n } must be understood as the term of index n in the sequence Δ a , and not Δ applied to the element a n .
Δ ( a n + 1 ) − Δ ( a n ) , (a_{n})=\Delta (a_{n+1})-\Delta (a_{n}),} yang dapat disederhanakan menjadi Δ 2 ( a n )a n + 2 − 2 a n + 1 + a n .
The second difference is Δ 2 a( Δ ∘ Δ ) aΔ ( Δ a ) .
Perbedaan kedua Δ 2 ( a n ) (a_{n})} didefinisikan sebagai Δ 2 ( a n )
Δ a n + ⋯ + ( k k ) Δ k ( a n ) .
Δ ( a n ) + ⋯ + ( k k ) Δ k ( a n ) .
See time scale calculus for a unification of the theory of difference equations with that of differential equations.
Lihat kalkulus skala waktu untuk penyatuan teori persamaan perbedaan dengan persamaan diferensial.
The linear recurrence of order d , a nc 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d ,c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},} has the characteristic equation λ d − c 1 λ d − 1 − c 2 λ d − 2 − ⋯ − c d λ 00.
Pengulangan linear order d, a nc 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d ,c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},} memiliki persamaan karakteristik λ d − c 1 λ d − 1 − c 2 λ d − 2 − ⋯ − c d λ 00. {
For example, when solving the initial value problem y ′ ( t )f ( t , y ( t ) ) , y ( t 0 )y 0 , )=y_{0},} with Euler's method and a step size h , one calculates the values y 0y ( t 0 ) , y 1y ( t 0 + h ) , y 2y ( t 0 + 2 h ) , …y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots } by the recurrence y n + 1y n + h f ( t n , y n ) , t nt 0 + n hy_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh} Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the discretization article.
Misalnya, saat memecahkan masalah nilai awal y ′ ( t )f ( t , y ( t ) ) , y ( t 0 )y 0 , )=y_{0},} dengan metode Euler dan ukuran langkah h , seseorang menghitung nilainya y 0y ( t 0 ) , y 1y ( t 0 + h ) , y 2y ( t 0 + 2 h ) , …y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots } oleh nilai y n + 1y n + h f ( t n , y n ) , t nt 0 + n hy_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh} Sistem persamaan diferensial orde pertama linier dapat didiskritisasi secara analitis menggunakan metode yang
SIAM Rev. Vol. 10, no. 3. pp.
SIAM Rev. Vol. 10, no. 3. hlm.
Concrete Mathematics: A Foundation for Computer Science (2 ed.).
Concrete Mathematics: A Foundation for Computer Science (Edisi 2).
Applied Econometric Times Series (3 ed.).
Applied Econometric Times Series (Edisi 3).
Archived from the original on 2014-11-10.
Diarsipkan dari asli tanggal 2014-11-10.
Mathematics for Economics and Business (Fifth ed.).
Mathematics for Economics and Business (Edisi Fifth).
Simulation, Modelling and Optimization, SMO'06. pp.
Simulation, Modelling and Optimization, SMO'06. hlm.
Archived from the original (PDF) on 2016-03-04.
Diarsipkan dari asli (PDF) tanggal 2016-03-04.