Recursion Relation is also know as Recursive Formula. Informal definition of recursion relation is the way to define series that each item defined by the previous items. But, to construct a complete recursion series, we need to define initial terms as precondition at first place. By its construction, it is easier to define rather than to answer what value of n in the series.
Further introductory can be explored in Recurrence Relations & Generating Functions by R. Knott
For $r \neq 1$, the sum of the first n of geometric series is:
$$a+ar+ar^{2}+ar^{3}+ \cdots +ar^{n-1}=\sum_{k=0}^{n-1}ar^{k}=a\left({\frac{1-r^{n}}{1-r}}\right)$$PROOF: a is initial term and r is common ratio.
$$\eqalign{ s&=a+ar+ar^{2}+ar^{3}+\cdots +ar^{n-1},\\ rs&=ar+ar^{2}+ar^{3}+ar^{4}+\cdots +ar^{n},\\ s-rs&=a-ar^{n},\\s(1-r)&=a(1-r^{n}), }$$So:
$${\displaystyle s=a\left({\frac {1-r^{n}}{1-r}}\right)\quad {\text{(if }}r\neq 1{\text{)}}.}$$As n goes to infinity, the absolute value of r must be less than one for the series to converge. The sum then becomes:
$$a+ar+ar^{2}+ar^{3}+ar^{4}+\cdots =\sum _{k=0}^{\infty }ar^{k}={\frac {a}{1-r}},{\text{ for }}|r|<1.$$When a = 1, this can be simplified to:
$$1\,+\,r\,+\,r^{2}\,+\,r^{3}\,+\,\cdots \;=\;{\frac {1}{1-r}},$$the left-hand side being a geometric series with common ratio r.
The formula also holds for complex r, with the corresponding restriction, the modulus of r is strictly less than one.
Proof of Convergence
We can prove that the geometric series converges using the sum formula for a geometric progression:
$${\displaystyle {\begin{aligned}1+r+r^{2}+r^{3}+\cdots \ &=\lim _{n\rightarrow \infty }\left(1+r+r^{2}+\cdots +r^{n}\right)\\&=\lim _{n\rightarrow \infty }{\frac {1-r^{n+1}}{1-r}}.\end{aligned}}}$$Since $(1 + r + r^2 + ... + r^n)(1−r) = 1−r^{n+1}$ and $r^{n+1} \rightarrow 0 \ \text{for} \ |r| < 1$
Convergence of geometric series can also be demonstrated by rewriting the series as an equivalent telescoping series. Consider the function,
$$g(K)={\frac {r^{K}}{1-r}}$$Note that
$${\displaystyle 1=g(0)-g(1)\ ,\ r=g(1)-g(2)\ ,\ r^{2}=g(2)-g(3)\ ,\ldots }$$Thus,
$${\displaystyle S=1+r+r^{2}+r^{3}+\cdots =(g(0)-g(1))+(g(1)-g(2))+(g(2)-g(3))+\cdots .}$$If,
$$|r| < 1$$then
$$g(K)\longrightarrow 0{\text{ as }}K\to \infty$$so S converges to:
$$g(0)={\frac {1}{1-r}}$$Let $n$ be a positive integer, and $x$ and $y$ real numbers (or complex numbers, or polynomials). The coefficient of $x^ky^{n-k}$, in $k^{th}$ term in the expansion of $(x+y)^n$, is equal to ${n \choose k}$, where:
$${n \choose k} = \frac{n!}{(n-k)!k!}$$So the Binomial Expansion is:
$$(x+y)^n = \sum_{r=0}^n {n \choose r} x^{n-r} y^r = \sum_{r = 0}^n {n \choose r} x^r y^{n-r}$$PROOF:
$$ \begin{align} (x+y)^n &= (x+y)(x+y)^{n-1} \\ &= (x+y)\bigg(\binom{n-1}{0} x^{n-1} + \binom{n-1}{1} x^{n-2}y + \cdots + \binom{n-1}{n-1}y^{n-1}\bigg) \\ &= x^n + \left( \binom{n-1}{0} + \binom{n-1}{1} \right) x^{n-1}y + \left( \binom{n-1}{1} + \binom{n-1}{2} \right) x^{n-2}y^2 \phantom{=} + \cdots + \left(\binom{n-1}{n-2} + \binom{n-1}{n-1} \right) xy^{n-1} + y^n \\ \end{align} $$and now Pascal's identity applies:
$$\binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k}$$So the right side simplifies to:
$$x^n + \binom{n}{1} x^{n-1}y + \binom{n}{2} x^{n-2}y^2 + \cdots + \binom{n}{n-1}xy^{n-1} + y^n$$The simplest type of recurrence reduce immediately to a product. The recurrence:
$$a_n = x_na_{n-1} \qquad \text{for} \ n>0 \ \text{with} \ a_0 = 1$$equivalent to:
$$a_n = \prod_{1 \leq k \leq n} x_k$$Theorem 2.1 (First Order linear Recurrences)
The recurrence
$$a_n = x_na_{n-1} + y_n \qquad \text{for} \ n>0 \ \text{with} \ a_0 = 0$$has the explicit solution:
$$a_n = y_n + \sum_{1 \leq j < n}y_jx_{j+1}x_{j+2}...x_n$$PROOF. Dividing both sides by $x_nx_{n-1}...x_1$ and iterating, we have:
$$ \eqalign{ a_n &= x_nx_{n-1}...x_1 \sum_{1 \leq j \leq n}\frac{y_j}{x_jx_{j-1}...x_1}\\ &= y_n + \sum_{1 \leq j < n}y_jx_{j+1}x_{j+2}...x_n } $$Simple convergence. One convincing reason to calculate initial values is that many recurrences with a complicated appearance simply converge to a constant. For example:
$$a_n = \frac{a}{(1+a_{n-1})} \qquad for \ n>0 \ with \ a_0 = 1$$This is a so-called continued fraction equation, which is discussed in §2.5. By calculating initial values, we can guess that the recurrence converges to a constant:
Each iteration increases the number of significant digits available by a constant number of digits (about half a digit). is is known as simple convergence. If we assume that the recurrence does converge to a constant, we know that the constant must satisfy $\alpha = \frac{1}{(1+\alpha)}$, or $1 - \alpha - \alpha^2 = 0$, which leads to the solution $\alpha = \frac{(\sqrt{5}-1)}{2} \approx .6180334$.
Recurrences where the right-hand side of the equation for $a_n$ is a linear combination of $a_{n-1}, a_{n-2},$ and so on.
For example:
$$a_n = 3a_{n-1} - 2a_{n-2} \qquad for \ n>1 \ with \ a_0 = 0 \ and \ a_1=1$$Solution:
$$ \eqalign{ a_n - a_{n-1} &= 2(a_{n-1} - 2_{n-2})\\ &= 2^{n-1}\\ a_n &= 2^{n}-1\\ } $$Another example:
$$a_n = 5a_{n-1} - 6a_{n-1} \qquad for \ n>1 \ with \ a_0 = 0 \ and \ a_1=1$$Has solution:
$$ \eqalign{ a_n - 3a_{n-1} &= 2(a_{n-1} - 3_{n-2})\\ &= 2^{n-1}\\ a_n &= 3^n - 2^n } $$Theorem 2.2 (Linear recurrences with constant coefficients)
$$a_n = x_1a_{n-1}+x_2a_{n-2}+...+x_ta_{n-t} \qquad for \ n \geq \ t$$Can be expressed as a linear combination (with coefficients depending on the initial conditions $a_0,a_1,...,a_{t-1}$):
$$q(z) \equiv z^t - x_1z^{t-1} - x_2z^{t-2} - ... - x_t$$PROOF. For $a_n = \beta^n$, where $\beta$ is a root of the "characteristic polynomial":
$$\beta^n = x_1\beta^{n-1} + x_2\beta^{n-2} + ... + x_t\beta^{n-t} \qquad for \ n \geq t$$or, equivalently,
$$\beta^{n-t}q(\beta) = 0$$That is, $\beta^n$ is a solution to the recurrence for any root $\beta$ of the characteristic polynomial.
Finding the coefficients. Develop theorem 2.2 to create a system of simultaneously equations that can be solved to yield the constants in the linear combination. For example:
$$a_n = 5a_{n-1} - 6a_{n-2} \qquad for \ n \geq 2 \ with a_0 = 0 \ and \ a_1 = 1$$The characteristic equation is $z^2 - 5z + 6 = (z-3)(z-2)$, so:
$$a_n = c_03^n + c_12^n$$Matching this formula against the values at $n = 0$ and $n = 1$, we have:
$$a_0 = 0 = c_0 + c_1$$$$a_1 = 1 = 3c_0 + 2c_1$$The solution to these simultaneous equations is $c_0 = 1$ and $c_1 = -1$, so $a_n = 3^n - 2^n$
Degenerate cases. When the coefficients turn out to be zero and/or some roots have the same modulus, the result can be somewhat counterintuitive. For example:
$$a_n = 2a_{n-1} - a_{n-2} \qquad for \ n \geq 2 \ with \ q_0 = 1 \ and \ a_1 = 2$$The characteristic equation is $z^2 - 2z + 1 = (z-1)^2$, so:
$$a_n = c_01^n + c_1n1^n$$We have:
$$a_0 = 1 = c_0$$$$a_1 = 2= c_0 + c_1$$gives $c_0 = c_1 = 1$, so $a_n = n + 1$.
Fibonacci numbers. ${0, 1, 1, 2, 3, 4, 8, 13, ...}$ is defined by prototypical second-order recurrence:
$$F_n = F_{n-1} + F_{n-2} \qquad for \ n>1 \ with \ F_0 = 0 \ and \ F_1 = 1$$roots of $u^2-u-1 = \phi = (1+\sqrt(5)/2 = 1.61803..$ and $\hat{\phi} = (1-\sqrt(5)/2 = -.61803...)$, Theorem 2.2 says that the solution is:
$$F_N = c_0\phi^N+c_1\hat{\phi}^N$$for some constants $c_0$ and $c1$:
$$F_0 = 0 = c_0 + c_1$$$$F_1 = 1 = c_0\phi + c_1\hat{\phi}$$yield the solution:
$$F_N = \frac{1}{\sqrt{(5)}}(\phi^N - \hat{\phi}^N)$$Nonconstant coefficients. If the coefficients are not constants, then more advanced technique are needed because Theorem 2.2 does not apply. For example:
$$\eqalign{ a_n &= na_{n-1} + n(n-1)a_{n-2} \qquad for \ n>1 \ with \ a_1 = 1 \ and \ a_0 = 0\\ \frac{a_n}{n!} &= \frac{na_{n-1} + n(n-1)a_{n-2}}{n!}\\ a_n &= n!F_n\\ }$$Change of Variables
For example:
$$a_n = \sqrt{a_{n-1}a_{n-2}} \qquad for \ n>1 \ with \ a_0 = 1 \ and \ a_1 = 2$$Let $b_n = lga_n$:
$$b_n = \frac{1}{2}(b_{n-1} + b_{n-2}) \qquad for \ n>1 \ with \ b_0 = 0 \ and \ b_1 = 1$$
Another example, for recurrence to continued fractions:
Iterating this recurrence gives the sequence:
$$\eqalign{ a_0 &= 1\\ a_1 &= \frac{1}{1+1} = \frac{1}{2}\\ a_2 &= \frac{1}{1 + \frac{1}{1+1}} = \frac{1}{1+\frac{1}{2}} = \frac{2}{3}\\ a_3 &= \frac{1}{1+\frac{1}{1 + \frac{1}{1+1}}} = \frac{1}{1+\frac{2}{3}} = \frac{3}{5} }$$That form, reveals the Fibonacci numbers. Let $a_n = b_{n-1} / b_n$:
$$\frac{b_{n-1}}{b_n} = 1 / (1 + \frac{b_{n-2}}{b_{n-1}}) \qquad for \ n > 1 \ with \ b_0 = b_1 = 1$$Dividng both sides by $b_{n-1}$ gives:
$$\frac{1}{b_n} = \frac{1}{b_{n-1} + b_{n-2}} \qquad for \ n > 1 \ with \ b_0 = b_1 = 1$$Repertoire
$$a_n = (n-1)a_{n-1}-na_{n-2}+n+1 \qquad for \ n>1 \ with \ a_0 = a_1 = 1$$Introducing a quantity $f(n)$ to the right-hand side:
$$a_n = (n-1)a_{n-1}-na_{n-2}+f(n)$$We arrive at the table:
| $a_n$ | $f(n)$ |
|---|---|
| 1 | 2 |
| $n$ | n - 1 |
| $n^2$ | n + 1 |
Subtracting the first row form the third gives the result that means that:
$$a_n = n^2 - 1 \qquad when \qquad f(n) = n-1\\ initial \ condition \ a_0 = -1 \ and \ a_1 = 0$$Now, we have two (linearly independent) solutions for $f(n) = n - 1$, which we combine to get the right initial values, yielding the result:
$$a_n = n^2 - n + 1$$Bootstapping
Given Fibonacci recurrence:
$$a_n = a_{n-1} + a_{n-2} \qquad for \ n > 1 \ with a_0 = 0 \ and a_1 = 1$$Note, that $a_n$ is increasing. Therefore, $a_{n-1} > a_{n-2}$ and $a_n > 2a_{n-2}$. Iterating this inequality imply the lower bound:
$$a_n > 2^{n/2}$$On the other hand, $a_{n-2} > a_{n-1}$ and $a_n < 2a_{n-1}$. Iterating this inequality imply the upper bound:
$$a_n < 2^{n}$$"guessing" a solution of the form $a_n \sim c_0\alpha^n$, with $\sqrt(2) < \alpha < 2$
Perturbation
$$a_{n+1} = 2a_n + \frac{a_{n-1}}{n^2} \qquad for \ n>1 \ with \ a_0=1 \ and \ a_1 = 2$$Eliminate $\frac{1}{n^2}$ because makes only a small constribution to recurrence, so:
$$a_{n+1} \approx 2a_n$$This a growth of the rough form $a_n \approx 2^n$ is anticipated. To make this preciese, consider the simpler sequence:
$$b_{n+1} = 2b_n \qquad for \ n>0 \ with \ b_0=1$$(so that $b_n = 2^n$) and compare the two recurrence by forming the ratio:
$$\rho_n = \frac{a_n}{b_n} = \frac{a_n}{2^n}$$From the recurrences, we have:
$$\rho_{n+1} = \rho_n + \frac{1}{4n^2} \rho_{n-1} \qquad for \ n>0 \ with \ \rho_0=1$$Clearly, the $\rho_n$ are increasing. To prove they tend to a constant, note that:
$$\rho_{n+1} \leq \rho_n (1+\frac{1}{4n^2}) \qquad for \ n \geq 1 \ so \ that \qquad \rho_{n+1} \leq \Pi_{k=1}^n (1+\frac{1}{4k^2})$$But the infinite product corresponding to the right-hand side converges monotonically to:
$$\alpha_0 = \Pi_{k=1}^\infty (1 + \frac{1}{4k^2}) = 1.46505...$$This, $\rho_n$ is bounded from above by $\alpha_0$ and, as it is increasing, it must converge to a constant. We have thus proved that:
$$a_n \sim \alpha \cdot 2^n$$for some constant $\alpha \le 1.46505...$
The number of comparisons used by mergesort is given by the solution to the recurrence:
$$C_N=C_{\lfloor{N/2}\rfloor}+C_{\lceil{N/2}\rceil}+N \qquad for \ N > 1 \ with \ C_1=0 \qquad (4)$$
Binary Search
The number comparisons used during an unsuccessful search with binary search in a table of size N in the worst case is equal to the number of bits in the binary representation of N.
$$B_N = B_{\lfloor{N/2}\rfloor}+1 \qquad for \ N \geq 2 \ with \ B_1 = 1$$Which exact solution is:
$$B_N = \lfloor{lgN}\rfloor + 1$$Exact solution of mergesort recurrence
The mergesort recurrence (4) is easily solved by differencing: if $D_N$ is defined to be $C_{N+1} - C_N$, the $D_N$ satisfied the recurrence:
$$D_N = D_{\lfloor{N/2}\rfloor}+1 \qquad for \ N \geq 2 \ with \ D_1 = 2$$which iterates to:
$$D_N = {\lfloor{lgN}\rfloor}+2$$and, therefore,
$$C_N = N - 1 + \sum_{1 \leq k < N} ({\lfloor{lgk}\rfloor}+1)$$Theorem 2.4 (Mergesort). The number of comparison used by mergesort is equal to $N - 1$ plus the number of bits in the binary representations of all the numbers less than $N$. Both quantities are described by the recurrence:
$$C_N=C_{\lfloor{N/2}\rfloor}+C_{\lceil{N/2}\rceil}+N \qquad for \ N \geq 2 \ with \ C_1=0$$Which has the exact solution $C_N = N{\lfloor{lgN}\rfloor} + 2N - 2^{{\lfloor{lgN}\rfloor} + 1}$.
PROOF
$$ \eqalign{ C_N &= (N-1) + (N-1) + (N-2) + (N-4) + ... + (N - 2^{{\lfloor{lgN}\rfloor} + 1})\\ &= (N-1) + N({\lfloor{lgN}\rfloor} + 1) - (1 + 2 + 4 + ... + 2^{{\lfloor{lgN}\rfloor} + 1})\\ &= N{\lfloor{lgN}\rfloor} + 2N - 2^{{\lfloor{lgN}\rfloor} + 1} } $$A variety of "devide-and-conquer" recurrence qrise that depend on the number and relative size of subproblems, the extent to which they overlap, and the cost of recombining them for the solution.
In pursuit of general solution, we start with the recursive formula:
$$\alpha(x) = \alpha a (x/\beta) + f(x) \qquad for \ x>1 \ with \ a(x) = 0 \ for \ x \leq 1$$defining a function over the positive real numbers. In essence, this corresponds to a divide-and-conquer algorithm that divides a problem of size x into $\alpha$ subproblems of size $x/\beta$ and recombines them at a cost of $f(x)$.
For example, consider the case where $f(x)=x$ and we restrict ourselces to the integers $N=\beta^n$. We have:
$$\alpha_{\beta n} = \alpha a_{\beta n - 1} + \beta^n \qquad for \ n > 0 \ with \ a_1 = 0$$Dividing both sides by $\alpha^n$ and iterating, we have the solution:
$$\alpha_{\beta n} = \alpha^n \sum_{1 \leq j \leq n} \left(\frac{\beta}{\alpha}\right)^j$$Theorem 2.5 (Divide-and-conquer functions). If the function $a(x)$ satisfies the recurrence:
$$a(x) = \alpha a (x/\beta) + x \qquad for \ x > 1 \ with \ a(x) = 0 \ for \ x \leq 1$$then
$$ \eqalign{ if \ \alpha < \beta &\qquad a(x) \sim \frac{\beta}{\beta-\alpha}x\\ if \ \alpha = \beta &\qquad a(x) \sim xlog_{\beta}x\\ if \ \alpha > \beta &\qquad a(x) \sim \frac{\alpha}{\alpha-\beta}\left(\frac{\beta}{\alpha}\right)^{{log_{\beta}\alpha}} x^{log_{\beta}\alpha} } $$Suppose that an algorithm attacks a problem of size $N$ by: