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

learn more… | top users | synonyms (2)

1
vote
2answers
61 views

Formula for calculating a progressive sum

If we say that initially the addition is $1$, the sum $0$ and $d$ is constant of $5$. step 1) ...
4
votes
1answer
42 views

How many matches are played?

A tennis club has $10$ couples as members. They meet to organize a mixed double match. If each wife refuses to partner as well as oppose her husband in the match, then in how many different ways ...
2
votes
2answers
55 views

Linear Recurrence In Faster Time

I am trying to solve this linear recurrence using matrix exponentiation:- $$f(n) = 2f(n-1) - f(n-2) + c,$$ where $c$ is a constant. What I have come up with is this - Let the matrix $M$ be $$ ...
0
votes
1answer
16 views

Help with recurrence relation and interest rates

how would I create a recurrence relation for the amount of money in a saving account after $n$ months $a_n$ , if the interest rate is $.5\%$ interest per month and initially the account has $\$1000$? ...
1
vote
0answers
15 views

Is it possible to have random number chain relation?

The real problem is like this.There are two equations executing in parallel. Can anybody help ? Ex: There are four random numbers 5 7 2 and 4. These numbers are related through a chain of relations ...
0
votes
2answers
35 views

are there any functions that fit this recurrence relation

Would anyone know if there any functions that fit this recurrence relation: $F_n = \frac{1}{n+3/2} \left ( F_{n+2} - c F_{n+1} \right )$ where $c$ is a constant parameter. or, more general: $F_n ...
4
votes
2answers
127 views

A summation involving multinomial coefficient

We need to find out $$\sum {\binom{N}{a_1,a_2,a_3...a_B} a_1^{\alpha}a_2^{\alpha}...a_C^{\alpha} }$$ $$a_1+a_2...a_B=N, \alpha>0 ,0\lt C \le B$$ All are nonnegative integers. We need to sum ...
6
votes
4answers
384 views

How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can ...
1
vote
2answers
28 views

particular solution of a difference equation

I am unable to find a particular solution of the following difference equation $$ y[k-1]-5y[k]+6y[k+1]=-u[k-1]+4u[k] $$ with $u[k]=\big(\frac{1}{2}\big)^k$. This is what I tried so far. Because ...
1
vote
1answer
17 views

How to find the generating function from recurrence relation $t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq, ~~n\ge 2$?

How to find the generating function $T(z)=\sum_{n=0}^{\infty} t_n~z^n$ from the recurrence relation $$t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq,\qquad n\ge 2.$$ given that $$t_1=b+(1+c~p)(a~q^{-1}+b),$$ ...
0
votes
3answers
47 views

Simple Linear Recurrence Relation Problems

$M(n)=3M(n−1)+1$ with base case of $M(1)=1$ Somehow I'm not understanding how to solve the recurrences. This problem is from my textbook and I was fine until I see this in example. I know it goes ...
1
vote
1answer
27 views

Linear recurrences relation

These are from my textbook examples, introduced as Theorem 1, If $T(n)=rT(n-1)+a,$ $T(0)=b$ and $r\ne 1$, $T(n)=r^nb+\left[\frac{a(1-r^n)}{(1-r)}\right]$ And I supposed to solve other ...
6
votes
1answer
316 views

Finding an explicit formula from a recursive formula.

I have the recurrence relation: $$g(k, 0, x) = k,$$ $$g(k, n, x) = \dfrac{1}{2} \log_{k}{\left(\dfrac{k^{g(k, n - 1, x)}x}{g(k, n - 1, x)}\right)},$$ and I would like to solve it, if it is ...
-1
votes
2answers
57 views

Summation Problems [closed]

How did this particular equation come about? I haven't seen it before in the summation rules index on wikipedia: $$\sum\limits_{i=1}^{k+1} x_i =\left(\sum\limits_{i=1}^{k} x_i\right)+x_{k+1} $$ ...
0
votes
1answer
76 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
2
votes
1answer
45 views

Recurrence relation involving infinite sequences.

How in general one would solve an infinite series recurrence relations? For instance, I am interested to solve the following: \begin{equation} \sum_{n=0}^{\infty} (-1)^{n} F(n)\{1-(\alpha n ...
0
votes
0answers
9 views

Simpler proof of Karp's Theorem for probabilistic recurrence relations?

A probabilistic recurrence relation is of the form $T(x) = a(x) + T(h(x))$ with $a(x)$ deterministic (usually $a(x) = 1$) and $h(x)$ being a random variable over $[0,x]$, so that $T(x)$ itself is a ...
0
votes
1answer
37 views

Recurrence involving square root

The recurrence equation I have is: $$ T_n = c_1 + T_{n-1} + 2\sqrt{c_2 + c_1 T_{n-1}} $$ $$ T_0 = a $$ $c_1,c_2,a$ are positive real numbers I need to somehow convert this into a linear homogeneous ...
0
votes
1answer
25 views

Number Theoretic Sum of three variables. Having trouble isolating two of them.

I encountered the following sum: $$\frac{c_{mn-p}}{c_0} = \sum_{d|p}\ \frac{a_{n-d}b_{m-\frac{p}{d}}}{a_0b_0} $$ Where $$a_i=0 \text{ when } i<0 \text{ and } b_j=0\text{ when } j<0\text{ and ...
1
vote
0answers
40 views

How to solve this kind of recurrence relation in closed form? $F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$

How to solve this recurrence relation in closed form? $$F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$$ I know how to solve recurrence relations for less than four calls by solving the ...
1
vote
1answer
41 views

Sum and product of linear recurrences

Given $a_n = \alpha_1 a_{n-1} + \cdots + \alpha_k a_{n-k}$ and $b_n = \beta_1 b_{n-1} + \cdots + \beta_l b_{n-l}$ are linear recurrences with complex coefficients, how can I find linear recurrences ...
3
votes
2answers
71 views

Closed form for solution of $t_{n+1}=t_n(t_n-2)$

As in the title I am interested in finding closed form for sequence satysfing $$t_{n+1}=t_n(t_n-2)$$ with $t_1=4$. I have tried many guesses, because I don't know if there is a metod to solve that, ...
0
votes
1answer
29 views

A closed form for the coefficients of Chebyshev polynomials

The Chebyshev polynomials are defined recursively: $T_0(x)=1$; $T_1(x)=x$; $T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$ I have been trying to find a closed form for the coefficient on the monomial $x^j$ of the ...
0
votes
1answer
38 views

Does the solution to $C_n = 2C_1 C_{n-1} - C_{n-2}$ can only be solved with $A = B = \frac{1}{2}$?

I was trying to solve the following recurrence in closed form (in terms of the initial conditions/base cases): $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ with base cases: $$ C_1 = C_1 $$ $$ C_2 = 2 C^2_1 ...
1
vote
1answer
52 views

Name of the numbers defined by $T(p,q) = T(p-1,q) + T(p,q-1)$?

I came across these numbers : $$ T(p,q)= \sum_{k=0}^{q-1} {p+k-1 \choose p-1} + \sum_{l=0}^{p-1} {q+l-1 \choose q-1} \quad p,q \in \mathbb{N} $$ While trying to solve this recurrence relation : $$ ...
2
votes
1answer
88 views

How to calculate the $n$-th member of sequence $a_{n+1}=\sqrt{y+a_{n}}$

I was searching for a smooth continuous concave function $$f:R^{+}\times R^{+}\to R^{+}$$ so that $$f(x+1,y)=\sqrt{y+f(x,y)}\quad\text{and}\quad f(0,y)=0.$$ But I couldn't find a general function, ...
0
votes
1answer
34 views

Find two linearly independent solutions of a Legendre equation about $x=0.$

Here is the statement of the problem: Consider the Legendre Equation $$ (*)\qquad (1-x^2)y''-2xy'+2y=0 $$ (a) Find two linearly independent solutions about $x=0$, solving completely any relevant ...
3
votes
0answers
67 views

How do i find formula for the recurrence relation :$x_{n+1}= x^2_{n}-x^2_{n-1}$ with :$x_{-1}=0,x_{0}=\frac{3}{4}$? [closed]

How do i find formula for the recurrence relation according to the below initial conditions: $x_{n+1}= x^2_{n}-x^2_{n-1}$ with :=$x_{-1}=0,x_{0}=\frac{3}{4}$ ? Note:$n=0,1,2\cdots$ Thank you for ...
4
votes
5answers
71 views

finding $a_1$ in an arithmetic progression

Given an arithmetic progression such that: $$a_{n+1}=\frac{9n^2-21n+10}{a_n}$$ How can I find the value of $a_1$? I tried using $a_{n+1}=a_1+nd$ but I think it's a loop.. Thanks.
0
votes
4answers
105 views

Limit of $\{a_n\}$, where $a_{n+1} = \sqrt{2+a_n}$ [closed]

I am struggling with this question: Let $\{a_n\}$ be defined recursively by $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Find $\lim\limits_{n\to\infty}a_n$. HINT: Let $L=\lim\limits_{n\to\infty}a_n$. ...
1
vote
1answer
57 views

Find recursive formula - Question from exam, check my answer

We want to demolish and move a bridge from one location to another. The bridge is made out of $m$ road segments all connected $[0,1]$, $[1,2]$, $[2,3]$...$[m-1,m]$ We have a given function $f$ which ...
1
vote
1answer
56 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
3
votes
2answers
242 views

Can the recurrence $C_n = 2 C_1 C_{n-1} - C_{n-2}$ be expressed in a closed expression?

I was wondering if the expression: $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ could be expressed as a closed expression in terms of (hopefully polynomials of) $C_1$ (or $C_2$). The bases cases for this ...
1
vote
1answer
19 views

Recursive Equation : $X_t=-\sum_{j=1}^{\infty}\phi^{-j}W_{t+j}$

$X_t=\phi X_{t-1}+W_t$ $\Rightarrow X_{t-1}=\frac{1}{\phi} X_{t}-\frac{1}{\phi}W_t$ Where , $|\phi|>1$ . But how does the following recursion relation occur : ...
4
votes
2answers
229 views

Recursive sequence of square roots of previous elements

Bruckner, Bruckner, Thompson - Elementary Real Analysis $a_1 = 1$ and $a_{n+1} = \sqrt{a_1+ a_2 + .. + a_n}$ Show that $$\lim_{n \to \infty}\ \frac{a_n}{n} = \frac12$$ I cannot untangle the square ...
1
vote
3answers
64 views

showing the limit of a recurrence relation

The recurrence relation is defined as such: $$a_n=2+\frac{80}{a_{n-1}}$$ It is also given that $a_1=2$, how do we show that $$\lim_{n\to\infty}a_n=10 ?$$ I am totally stuck at how I should approach ...
0
votes
1answer
12 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
0
votes
1answer
60 views

Tiling problem : Number of ways a floor can be tiled

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even) Could you please help in ...
0
votes
1answer
17 views

Recurrence Relations with ternary strings

Find and solve a recurrence equation for the number gn of ternary strings of length n that do not contain 102 as a substring. I am having some trouble finding the recurrence relation for this ...
2
votes
3answers
44 views

Finding an explicit formula for a recursive sequence. [closed]

How to show that the recurrent formula $$A_n=A_{n-1} + A_{n-2} +4.$$ gives a sequence of the form $f(n)=cr^n+cr^n$? The only way we are allowed to solve it, is with the quadratic formula ...
3
votes
1answer
34 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
1
vote
0answers
38 views

solving a linear recurrence relation simple moving average

Here's a recurrence relation, $k$ is fixed: $$\frac{1}{k}\sum_{n=i}^{k+i-1} a_n = a_{k+i}$$ for all $i\in \mathbb{N}$, and for $a_i$ with $1\leq i \leq k$ we have fixed non-negative real number ...
1
vote
2answers
61 views

Solving recurrence using analogy with continuous $x_{n+1} = \frac{r^2}{2d - x_n}$

What's up lovely friends, I'm facing a physics problem and felt on a recurrence that one does not see everyday. This one: $x_{n+1} = \frac{r^2}{2d - x_n}$ or $f(n+1) = \frac{a}{b-f(n)}$ if you will ...
2
votes
0answers
38 views

Solving this recurrence relation representing constant-power loads on a resistive cable

Given the following: $$\begin{align} v_n&=v_{n-1}-r\sum_{i=n}^m \frac p{v_i}\\ v_0&=V \end{align}$$ where: $$\begin{align} m\ge n\ge 0\;&:\;m,\,n\in\mathbb {N_0}\\ ...
5
votes
3answers
143 views

Prove that $A_{100} \gt 14$ where $A_{n}=A_{n-1}+\frac{1}{A_{n-1}}$ and $A_1=1$

I tried attempting the question, and the best upper bound I could obtain was $1+\ln{98}$. I tried using $A_{n}\le n$ to form a harmonic series, but that wasn't strong enough. Any help would be ...
3
votes
1answer
30 views

Solving recurrence relation with repeating roots

I am aiming to solve this recurrence relation and I have chosen the Characteristic Equation method: $d_n = 4(d_{n-1}-d_{n-2})$ with $d_0 =1, d_1=1 $ Finding the C.E. I get: $x^2-4x+4=0$ Solving for ...
0
votes
2answers
25 views

Recurrence relation complexity

I just learned about recurrences and I just can't solve this problem. I have this recurrence relation: $T(n)=k * T(n / k)$ $T(0)=1$, where k is a constant number. I tried drawing a recurrence tree ...
8
votes
1answer
155 views

Finding closed form for a generating function with different powers of $x$ in parameter

I'm working on a math/programming puzzle that involves an integer series defined as having a recurrence relating values $a(n)$ to $a(\lfloor\frac{n}{2}\rfloor)$ and $a(\lfloor\frac{n}{4}\rfloor)$. ...
2
votes
1answer
23 views

Are there variants (described below) of $3n + 1$ conjecture where the answer is known?

The $3n + 1$ conjecture states that if you take any natural number $n_j$, and if it is even then set $n_{j+1} = n_j/2$, otherwise set $n_{j+1} = 3n_j + 1$, then no matter what natural number $n_0$ you ...
2
votes
2answers
61 views

Product of Matrices I

Given the matrix \begin{align} A = \left( \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right) \end{align} consider the first few powers of $A^{n}$ for which \begin{align} A = \left( ...