# Tagged Questions

Questions regarding functions defined recursively, such as the Fibonacci sequence.

12 views

### limit of $a_n$ when n to infinity. $a_1=\sqrt{k}$ and $a_n = \sqrt{k}^{a_{n-1}}$ . $0<k<1$.

I find a question on quora: limit of a sequence. Generalized Case 1 When you generalize this question like: \begin{align} a_1 &= \sqrt{k} \\ a_n &= \sqrt{k}^{a_{n-1}} \end{align} ...
30 views

### Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$T_1=1=n=1$$ Assume true for$n = ...
25 views

### Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$. I've found the characteristic equation to ...
42 views

### Find a close form expression for $f(x)$

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side ...
1k views

### Non-homogeneous linear recurrence relation

I have this recurrence relation to solve: $$a_{n+1}=3a_n+2^{n-1}-1.$$ The homogeneous part's solution is obviously $a_n=k3^n.$ Now I don't know how to solve the original equation, but I do know what ...
25 views

### Recurrence relations, stability of orbits [on hold]

I have a problem with following task. How to show existence of orbits with period 2 and check for which values of parameter $a$ they are stable at this recurrence relation: $x_{n+1}=ae^{-4x_{n}}$. Any ...
38 views

11 views

### Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
94 views

### Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
63 views

### Power series solution (Why the constant of the recurrence relation can be chosen arbitrarily?)

Please help me understand this: Solve $(x+1)y''-(2-x)y'+y =0$ First, since $x_0=0$ is an ordinary point, it can be guaranteed that we can find two independent power series solutions centered at ...
8 views

### Explicit solution for a non-linear recurrence equation

Does the following non-linear recurrence equation has an explicit solution with given boundary conditions $x_0$ and $x_\infty$? $$x_n = a + b x_{n-1}x_{n+1}$$ $a$ and $b$ are constants.
65 views

### Solving a series of equations

I'm writing a piece of code to translate some data, and I keep banging my head against the wall with a one part of the transformation. I'm not as good at math as I ought to be :) Say we have a ...
16 views

### Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
30 views

### Series with recursive terms: reciprocal of the sums of previous terms

What are some references and material that are devoted to studying series of the form $x_1+\frac1{x_1}+\frac{1}{x_1+\frac1{x_1}}+\dotsc$ where $x_1>0$ is given? For instance, my (non math) friend ...
31 views

### Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the ...
30 views

### Finding “equilibrium”

Say I have three amounts $A$, $B$ and $C$. And a set of conversions between them $K_{A->B}$, $K_{B->A}$ and $K_{B->C}$. The conversions denote what fraction and at what efficiency they ...
21 views

### Proving running time with induction

I need to use induction to prove the run time of the given recurrences: $T(1) = c_1$ $T(n) = T(n-1) + c_2$ Well this is the first time Im doing induction on this kind of exercise - I would like ...
25 views

16 views

### Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
62 views

### A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where $$S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}.$$ ...
93 views

### General solution of a finite-difference equation with real non-commensurable differences.

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
272 views

### Is there an easy way to see that this simple recurrence is 9-periodic?

In a colloquium talk yesterday, Robert Bryant pointed out that for all initial values $a_0, a_1 \in \mathbb{R}$, the sequence generated by the recurrence relation $$a_{n+1} = |a_n| - a_{n-1}$$ turns ...
6 views

### How to solve a difference equation with an input?

How do you solve the difference equation (initial conditions are given) $$y(k)+ay(k-1)+by(k-2)=cx(k-1)+dx(k-2)$$ where the input $x(k)=\theta(k)$ (the unit step function). I know that the general ...
15 views

### First-order Taylor series expansion

I have a first-order equation that is supposed to be solved using the Frobenius method. I am having some difficulty since the equation is not equal to zero. I would appreciate any help. y' + (1 - ...
1k views

### Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
48 views

### Solving a Recurrence Relationship

Given recurrence relationship: $g(1) = 5;\\ g(2n) = 4g(n);\\ g(2n+1) = 4g(n).$ I feel lost because of $g(2n)$ and $g(2n+1)$. Based on my coursebook, there is the common standard form, which can be ...
10 views

25 views

### Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
30 views

13 views

### Solving recurrence relations question? [duplicate]

Hey I dont know how to do this question. Can any pls show me the working out for these question. Questions: http://pasteboard.co/uSZZRst.jpg
16 views

### Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z$ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
28 views

### Recurrence Relation With Non-constant Coefficient

I have a question that involves finding the closed form of the generating function for this sequence $$na_n = 3a_{n-1} -4a_{n-2}+ \frac{8.3^{n-2}}{(n-2)!}$$ with $$a_0=2, a_1=6$$ My lecturer told me ...
951 views

### expansion of $\cos^k(\theta)$

Does any body know a expansion of : $\cos^k(\theta)$ in function of $\cos$ and/or $\sin$ but without power? For example : $\cos^2(\theta)=\frac{1}{2}(\cos(2\theta)+1)$, but i would want a ...
33 views

### Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $c_n = C_12^n+C_23^n.$ The particular solution is in the ...
36 views

### How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...
29 views

### Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
### Find limit recursion of sequence $x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1}$
Prove sequence $$x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1}$$ $$x_0 = 0, x_1 = 1$$ converges and find it's limit My attempt Let's prove $0 \le x_n \le 1$: $x_n \ge 0$ (obvious) By ...
I'm working on a problem that I've managed to reduce to a third-order homogeneous recurrence relation given by the following expression: (n + 3) f_{n + 3} - 2(n + 2) f_{n + 2} + (n - 1) f_{n + 1} + ...