Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recurrence-relations]

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

1
vote
0answers
21 views

How to obtain recursion relations from this

I'm trying to solve a problem using the power series solution. Finally (and after substitution of differentations) I have come up with $$ -\frac1{2\mu}\sum_{i=2}^p i(i-1)a_i r^{(i+l-1)}+\frac1{2\mu}\...
0
votes
1answer
26 views

A specific and interesting recurrence relation

Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n&...
-1
votes
0answers
26 views

Derivative of integral for non-negative part functions

Suppose we have $N$ random variables $u_1,u_2,...,u_N$, which are i.i.d with PDF $f(\cdot)$. Then how to compute the partial derivative of $g(x,y)$ with respect to $x$ and $y$? That is, $\frac{\...
1
vote
1answer
32 views

searching for a formula for $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$

So we have a number $n$, which is a power of two. And we have the following recursion: $$ T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$$ I solved some exercises like this, but I have a problem with ...
1
vote
1answer
48 views

Give a closed formula for the recursive series of $S_1 = \frac{a_1}{b_1}, S_{n+1} = \frac{a_{n+1}}{b_{n+1}+S_n}$

The Problem: The following real numbers are given: $$a_1,a_2,a_3,...\in\Bbb{R}\backslash\{0\} \\ b_1,b_2,b_3,...\in\Bbb{R}\backslash\{0\}$$ We define a recursive series of: $$S_1 = \frac{a_1}{b_1} ...
0
votes
0answers
33 views

Solve the recurrence relation: $T(n) = T(n - \sqrt{\mathstrut n}) + T(\sqrt{\mathstrut n}) + O(n)$

I think that $T(\sqrt{\mathstrut n})$ part is $O(log(log(n)))$ but I cannot solve the whole problem. . Can anyone help? Edit: The formula appears while solving the following problem: If in quick-...
0
votes
1answer
21 views

Convergence of series $a(n)$, where $a(n+1) = p + qa(n)$, $n \geq 1$

Suppose for $n \geq 1$, we have for some constants $p,q$ $a(n+1) = p + qa(n)$. Conditions on $p$ and $q$ for which the series converges? So, we have the series as $a(1)+a(2)+a(3)+\ldots $ $a(1) +...
1
vote
1answer
33 views

Proving Recurrence formula takes integer values

Let $f_0=1$, $f_1=1$, $f_2=1$, $f_{n}=\frac{f_{n-1}f_{n-2}+1}{f_{n-3}}$ for $n\geq{3}$ Prove that $f_n$ is always an integer. I tried to use induction, but the calculations were messy and ...
0
votes
0answers
14 views

Power Series Solution for deriving a recursion relation

Unfortunately, I'm not familiar with Power series solution method. Also reading some guide files did not help me much. I hope you offer me some hints. I have an equation as follows $$ [- \frac{d^2}{dr^...
1
vote
1answer
36 views

Extracting coefficients from two-dimensional generating function

We have the two-dimensional recurrent series $F(r+1,s+2) = F(r,s) + F(r,s+1) + F(r,s+2)$ and the boundary conditions $F(r,0)=1$, $F(0,s)=0$ for all $s>0$ and $F(0,0)=1$ and $F(r,1)=r$. This series ...
0
votes
1answer
45 views

Deriving a recursion relation

I have read a paper which drives a recursion relation as follows and starting from Eq.(1) $$ [- \frac{d^2}{dr^2}+\frac{l(l+1)}{r^2}+\frac{\omega^2}{4}r^2+\frac{\zeta}{r}]\,\phi_{nl}(r)=E^r_{nl}\,\phi_{...
0
votes
0answers
23 views

Prove $O(\frac{1}{T})$ convergence rate

Suppose we have the following first-order non-homogeneous recurrence relation $$z_{t+1} \leq \frac{1}{(1+b_1c_t)^2}\big(\left(1+b_2c_t^2 \right)z_t + b_3c_t^2\big) $$ where $t$ is an integer which ...
1
vote
1answer
27 views

Plotting an iterative system of nonlinear equations using MATLAB

Consider the following coupled system: Let $x(n) = \left[ \begin{array}{c} x_1(n)\\ . \\ .\\ .\\ x_{32}(n) \end{array} \right]$, and the system of $32$ first order nonlinear ...
0
votes
1answer
17 views

Recurrence relation general solution

I am sorry I'm posting this on phone, I have the recurrence an = 5an−1 − 6an−2 + 7^n When solved with the method of particular solution coefficient of 7^...
0
votes
1answer
23 views

Why is this eigenvalue problem solved by $\phi(r) = J_v(\alpha r)$

I can't seem to see how the bessel function $J_v(ar)$ solves the problem. The eigenvalue problem has an $\alpha^ 2\phi(r)$ term Ive tried writing $x = \alpha r$ in the expression for $J$ but cant ...
0
votes
1answer
26 views

How to solve a recurrence relation for a bit string of length n that starts with 1?

I am doing a homework assignment and am stuck on the following problem: Find a recurrence relation and give initial conditions for the number of bit strings of length n begin with 1. I'm not sure how ...
4
votes
4answers
212 views

Closed form of recurrent arithmetic series summation

Knowing that $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ how can I get closed form formula for $$\sum_{i=1}^n \sum_{j=1}^i j$$ or $$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j k$$ or any x times neasted ...
-1
votes
3answers
38 views

How to solve the following recurrence equation: $ a_{n+1} =2^n \cdot a_{n}$? [closed]

How to solve the following recurrence equation: $$ a_{n+1} =2^n \cdot a_{n}$$ Could you help me?
0
votes
0answers
21 views

help solving the following non-homogenous recurrence relation (solution provided)

I do not understand how A and B are calculated, but I get the rest. Can someone show me how to calculate A and B?
1
vote
1answer
55 views

Asymptotic Solution of Recurrence Relations

I have a recurrence relation, \begin{align} 0 \leq A_{n+1} \leq A_n - c_1 {A_n}^{m} + \frac{c_2}n, ~~~\forall n\geq 1\label{rec}\tag{1} \end{align} where $c_1$ and $c_2$ are positive constants, and $...
1
vote
1answer
26 views

Convergence of a recursive sequence implies a span

I am studying for a final in linear algebra and a practice problem that was posed is the following: Let $a_1,a_2\in R$ (R is the set of reals). For $n\geq 3$, set $a_n = \frac{5}{2}a_{n-1}-a_{n-2}$....
1
vote
1answer
30 views

How to solve the following non-homogenous linear recurrence relation

find the particular solution for: can someone show me how to get the answer for this?
0
votes
1answer
22 views

Prove the statement, For all integers $n ≥ 0$, $y_n = 3 * 2^n + 4^n$ where $y_0 = 4, y_1 = 10$ and when $n ≥ 2$, $y_n = 6y_{n-1} – 8y_{n-2} $

So approaching this problem For all integers $n ≥ 0$, $y_n = 3 * 2^n + 4^n$ where $y_0 = 4, y_1 = 10$ and when $n ≥ 2$, $y_n = 6y_{n-1} – 8y_{n-2} $ I realise that is probobly needs to be proved ...
2
votes
4answers
89 views

Infinitely many integer solutions of a cubic equation

Is it true that there are infinitely many pairs of integers $(m,n)$ such that $m^3 + 5n^3 + m^2n = 1$? Or maybe $m^3 + 5n^3 + m^2n = -1$? The point is that I am trying to find a description of an ...
4
votes
3answers
92 views

Stirling numbers of second kind, but no two adjacent numbers in same part.

Update: The problem has been solved. @Phicar and I individually give two transformation from $h\rightarrow S$ and $S\rightarrow h$, and they are inverse of each other. Any other explanation or ...
0
votes
1answer
61 views

Can anyone solve this recurrence equation?

I would like to model compound interest where in each period part of the existing capital can be used to increase the annual interest rate. At first I tried to model this in a way such that in each ...
1
vote
2answers
43 views

Divergence or convergence of a recurrence sequence using differential equations

We have a recursive sequence $y_{n+1} = \sqrt{\frac{n+3}{n+1}} y_{n}$ for which value of $y_0$ does it converge? I found this question in a set of Differential Equation problems. I don't have any ...
10
votes
5answers
1k views

Why does this iterative way of solving an equation work?

I was solving some semiconductor physics problem and in order to get the temperature I got this nasty equation: $$ T = \dfrac{7020}{\dfrac{3}{2}\ln(T)+12}.$$ It seems that I can solve this kind of ...
0
votes
2answers
18 views

Backward substitution of a difference equation

I was trying to understand the intuition behind this. I understand how the following reccurence was done: $$X_{t} = \alpha X_{t-1} + C^{2}$$ $$ \alpha X_{t-1} = \alpha X_{t-2} + C^{2} $$ $$ \alpha^{...
1
vote
1answer
53 views

Generating function of recurrence relation $T(n) = T(n-1) + (n-1)$

Generating function of recurrence relation $T(n) = T(n-1) + (n-1)$ I've been trying to get the closed form for this recurrence by using generating function, and got to the following $$ G(x) - xG(x) -...
8
votes
1answer
149 views

Prove that $x_n$ and $n$ are coprimes

I'm here again with a problem of Italian National Math Olympiads 2007. Given the following subcession: Given the following succession $$\left\{\begin{matrix} x_1=2\\ x_{n+1}=2x_n^2-1 \end{...
-1
votes
1answer
29 views

How to solve recurrence relations involving integrals?

Suppose we have two sequences $C_i$ and $f_i$, where $C_0=\frac{\pi^2}{3}$ and $f_0=i\pi x$ and with the recurrences $$f_{n+1}(x)=\int \left( \int ( f_n(x) + C_n ) dx \right)dx$$ where the integrals ...
0
votes
1answer
23 views

Linear recurrence sequence in F2

Currently, I'm solving this exercise: Let $s= (s_0,s_1,s_2,...)$ be a linear recurrence sequence in $F_2$ with recurrent relation $s_{n+3}+s_{n+1}+s_n= 0$, for $n\in \mathbb N$. Now my (...
1
vote
1answer
90 views

Recursion with three variables.

For u(a,b,c) is a function of a,b,c $\in Z $, We have the recursive relationships: $$u(a,b,c)=1/6[u(a-1,b+1,c)+u(a-1,b,c+1)+u(a,b-1,c+1)+u(a+1,b-1,c)+u(a,b+1,c-1)+u(a+1,b,c-1)]+1$$ and constraints: ...
0
votes
3answers
42 views

Use generating functions to solve the recurrence relation

Use generating functions to solve $a_n = 3a_{n-1} - 2a_{n-2} + 2^n + (n+1)3^n$. What I have so far, not sure if I forgot to do something or am missing out on something obvious: Define $$G(x) = \sum_{...
1
vote
1answer
30 views

Discrete Mathematics Recursion

A bacteria colony begins with $6$ individuals and doubles in size every hour. Write down a recurrence for a population at the beginning of hour n, and solve it. How many hours elapse until the ...
2
votes
4answers
56 views

Is there some strategy to find the general term of a recursive sequence?

Given $(a_{n})_{n \in \mathbb{N}}$, $a_{0} = 2, a_{1} = 4, a_{n+2} = 4a_{n+1} - 3a_{n}$, is there any way to find the general term? I reckoned that every $a_{i}$ is a factor of 2, and then the ...
1
vote
2answers
60 views

Generating function of $\frac{h(x)}{(1-x)^2}$

If $h(x)$ is the generating function for $a_r$, what is the generating function of $$\frac{h(x)}{(1-x)^2}$$ Let $h(x)$ be written as $$h(x) = \sum_{r} a_r x^r $$ Consider more simply $$\frac{h(x)}{...
2
votes
0answers
23 views

Conjecture on the growth of $q_1 = 1, q_{n+1}=q_n + f(q_n) $

This is a generalization of my answer to Calculate the limit of the following recurrent series in the form suggested by Will Jagy. $q_1 = 1, q_{n+1}=q_n + f(q_n) $ where $f(x) > 0$ and $f'(x) <...
1
vote
1answer
39 views

Recurrence relation of partioning $n$ into exactly 3 parts:

I wanted to find a recurrence relation for partitioning an integer $n$ into exactly $3$ parts To be clear, I know the formula $P(n,k)=P(n-1,k-1)+P(n-k,k)$, but I want to derive a relation involving ...
0
votes
1answer
42 views

Understanding the recurrence relation T(n) = c(T(n/c) + 1)

Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation. Think about inputs of the form $c^k$. $$T(c^k)=cT(c^{k-1})+c=c^2T(c^{k-2})+c^2+...
0
votes
1answer
25 views

On a method to solve certain recursive sequences - looking for counterexamples?

When I started with this question, I wanted to know why my reasoning was wrong. Nevertheless, after checking some examples, I've noticed that my conjecture was actually - or at least seems to be - ...
1
vote
0answers
31 views

Number of different ways in which you can have 'c' parts (not necessarily rectangular) of a rectangular board

You are given a rectangular board of $A$ rows where each row contains $B$ square shaped boxes. Each square box has a unique integer written on it in the row major order (starting from $1$ to $A\cdot B$...
-1
votes
2answers
34 views

How to solve quadratic recurrence relation

How to solve recurrence relation of the following form: $U_n = a \times U_{n-1}^2 + b \times U_{n-1} + c$ where: $-1 < a < 0$ , $b = 1 - a$ , $c > 0$
0
votes
1answer
49 views

Solve the recurrence relation $T(n) = c(T(n/c) + 1), T(1) = 1$, by finding an expression for $T(n)$ in big-Oh notation.

I'm a complete beginner at this, and was having trouble with this problem. looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of f(n) = af(n/b) + Cnd I think the master theorem ...
1
vote
1answer
44 views

combinatorics - recurrence relations

I tasked with solving the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ given the initial conditions $a_0 = 1, a_1 = 4$. I do not know how to begin here. However, I know that $$a_2 = 14,$$ $$a_3 = ...
0
votes
1answer
50 views

How do you solve a linear recurrence relation for $a_{n}$ given the solution

I'm a beginner who is starting to learn about linear recurrence relations. I've just come across a problem where I'm not sure how to progress. Going off of my notes linear recurrence was solved ...
2
votes
1answer
93 views

Are these statements always true?

I haven't found an answer in my books. Although the question seems very simple, I want to ask. Are these statements always true? a) For any infinity non-negative integer sequence, if there is an ...
1
vote
1answer
50 views

Find the solution of the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n+n+3$?

Using the characteristic equation $r^2=4r-3 \to r^2-4r+3=(r-3)(r-1)$ results in roots $1,3$. I show that $a_n^{(h)}=\alpha_1+\alpha_23^n$ I'm having a hard time understanding how to handle the non-...
4
votes
1answer
46 views

How can I make sure the recurrence relation is correct?

If $A_n$ represents the number of ways to write $n$ as an ordered sum of positive odd integers, then $A_n = A_{n-1} + A_{n-2}$. For example, $A_2 = 1$ $(1+1)$, $A_3 = 2$ $(1+1+1)$, $(3)$, and $A_4 ...