closed form

A closed form function which gives the value of a sequence at index $n$ has only one parameter, $n$ itself. This is in contrast to the recurrence relation form, which can have all of the previous values of the sequence as parameters.

The benefit of the closed form is that one does not have to calculate all of the previous values of the sequence to get the next value. This is not too useful if one wants to print out or utilize all of the values of a sequence up to some $n$ , but it is very useful to get the value of the sequence just at some index $n$ .

There are many techniques used to find a closed-form solution for a recurrence relation. Some are

•
Repeated substitution. Replace each $s_{k}$ in the expression of $s_{n}$ (with $k<n$ ) with its recurrence relation representation. Repeat again on the resulting expression, until some pattern is evident.
•
Estimate an upper bound for $s_{n}$ in terms of $n$ . Then, solve for the unknowns (say there are $r$ unknowns) by finding the first $r$ values of the recurrence relation and solving the linear system formed by them and the unknowns.
•
Find the characteristic equation of the recurrence relation and solve for the roots. If the recurrence relation is not homogeneous, then you’ll have to apply a method such as the method of undetermined coefficients.

单词	ClosedForm
释义	closed form A closed form function which gives the value of a sequence at index $n$ has only one parameter, $n$ itself. This is in contrast to the recurrence relation form, which can have all of the previous values of the sequence as parameters. The benefit of the closed form is that one does not have to calculate all of the previous values of the sequence to get the next value. This is not too useful if one wants to print out or utilize all of the values of a sequence up to some $n$ , but it is very useful to get the value of the sequence just at some index $n$ . There are many techniques used to find a closed-form solution for a recurrence relation. Some are • Repeated substitution. Replace each $s_{k}$ in the expression of $s_{n}$ (with $k<n$ ) with its recurrence relation representation. Repeat again on the resulting expression, until some pattern is evident. • Estimate an upper bound for $s_{n}$ in terms of $n$ . Then, solve for the unknowns (say there are $r$ unknowns) by finding the first $r$ values of the recurrence relation and solving the linear system formed by them and the unknowns. • Find the characteristic equation of the recurrence relation and solve for the roots. If the recurrence relation is not homogeneous, then you’ll have to apply a method such as the method of undetermined coefficients.
随便看	weak convergence WeakConvergenceInNormedLinearSpace weak* convergence in normed linear space WeakDerivative weak derivative WeakDimensionOfAModule weak dimension of a module WeakerVersionOfStirlingsApproximation weaker version of Stirling’s approximation WeakestExtensionOfAPartialOrdering weakest extension of a partial ordering WeakGlobalDimension weak global dimension WeakHomotopyDoubleGroupoid weak homotopy double groupoid WeakHomotopyEquivalence weak homotopy equivalence WeakHopfAlgebra weak Hopf algebra WeakHopfCalgebra weak Hopf C*-algebra WeaklyCompactCardinal weakly compact cardinal WeaklyCompactCardinalsAndTheTreeProperty weakly compact cardinals and the tree property