Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
21 views

Counting with Recurrence Relations

Find the recurrence relation for a(n) - number of ternary strings of length n, containing the number 2 odd times. Some of these: 012,112,12,02,... .
1
vote
3answers
56 views

How do I solve the non-homogeneous recurrence relation $f(n) = f(n-3) +1$?

This is part of a question from my combinatorics homework I've been trying to solve for a few days now... The initial conditions are: f(0)=f(1)=f(2)=1 I tried first to solve the homogeneous part by ...
-1
votes
0answers
27 views

How would I write this system of recurrence relations in matrix form?

I have the following system of recurrence relations: $$ p_{t+1}(i)=p_0(i)+\sum_{j\in W_{*i}^{vp}}v_t(j)W_{ji}^{vp},\\\ v_{t+1}(i)=v_0(i)+\sum_{j\in W_{*i}^{pv}}p_t(i)W_{ji}^{pv}+\sum_{k\in W_{*i}^{ev}...
0
votes
0answers
31 views

Finding a recurrent relation or formula

The formulation of the original problem: "How many words can be made up of N sticks, if two sticks can make the letter i, and three sticks can make j?" Final task: create a formula (or recurrent ...
0
votes
0answers
20 views

General question about the connection between the location of roots of polynomial and eigenvalues of its characteristic polynomial

Maybe my problem is a general thing. So I write it really generaly. I have a recursively defined polynomial $P_n(x)$ where I am able to use the technique of constructing the linear combination $$P_n(...
0
votes
0answers
17 views

Random walk and stationary distribution

I wonder what types of random walk have stationary distributions? I have come across random walk examples in lecture where the states are all null recurrent for dimension 2 and lower, transient in ...
0
votes
0answers
21 views

validation of third variation on Fibonacci’s rabbit sequence

Here is a third variation on Fibonacci’s rabbit sequence. We begin with one pair of newborn rabbits. Once the pair is three months old, the pair has one pair of offspring, and continues to have one ...
-3
votes
1answer
29 views

Please help to provide hint for the following questions [closed]

You borrow $18,000 to buy a car. The finance rate is 4% per year. You will make payments over 3 years. At the end of each month you will repay an amount b (in dollars), to be determined. Let an be the ...
0
votes
0answers
22 views

Minimizing a function from future dependencies

Given $f(i) = min(a + f(i+1), b + f(i+5), c + f(i+10))$ By using above relation, can we find the relation for $f(i)$ on it's previous values i.e., $f(i) = min(a + f(i-1), b+ f(i-5), c+f(i-10))$ or ...
0
votes
0answers
6 views

Why does gap in plot identify region with possible roots of recursively defined polynomial.

I am interested in the interval of $x$ where roots of a recursively polynomial can be found. Lets define a recursive polynomial as: $$P_0(x) = 1$$ $$P_n(x) = x \sum\limits_{k=1}^{n} k P_{n-k}(x)$$ ...
0
votes
1answer
25 views

Fibonacci Rabbit's variation

Okay so I am trying to understand modifications to the famous fibonacci rabbit problems so I can make a generalized website for it as a pet project, where people just need to input paramaters and it ...
0
votes
0answers
13 views

How to confirm the nth Catalan Number given the first few values in the sequence?

Given $Y_0 = 1$, $Y_1 = 1$, $Y_2 = 2$, $Y_3 = 5$, $Y_4 = 14$, $Y_5 = 42$, $Y_6 = 132$; what are three different ways to confirm that $Y_r$ may possibly be the nth Catalan number for all $r$. Describe ...
2
votes
4answers
47 views

Solving $a_{n}a_{n-1}=1,\, a_1=2$

The solution of the recurrence $$a_{n}+a_{n-1}=1,\, a_1=2$$ is $$a_n=\frac{1-3(-1)^n}{2}.$$ Could this be somehow used to solve $$a_{n}a_{n-1}=1,\, a_1=2?$$ Logarithms would turn this to $$\ln a_n+\ln ...
1
vote
1answer
21 views

Interpolation recurrence relation limit

I'm dealing with a problem (background at the end) where I'm using linear interpolation. I'm trying to figure out number of steps required to get within a specified limit, and the interpolation factor ...
0
votes
0answers
6 views

Proof of Linear Homogenous Recurrence Relations with constant coefficient and with two distinct roots

I was going through the book "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the proof the following theorem. The backward proof is fine but I did not feel the forward ...
0
votes
1answer
23 views

Find recursive formula for number of sequences that meet criteria

I am given such a problem: Find the number $a_n$ of n-element ternary sequences (composed only of 0s, 1s and 2s), where: a) There are no repetitions of 1 (two 1s cannot stand next to each other) b) ...
-3
votes
0answers
28 views

Can someone help me with recurrence? [closed]

How can I solve the recurrence relation? Thank you! $$f(n)=25f (\frac{n}{5})+ \frac {n^2}{\log n}$$ I am wondering how to apply the Master Theorem here. Does this satisfy the first case in master ...
1
vote
0answers
20 views

Help solving a recurrence relation?

Here is the relation- $$jB(n,j)=(j+2)(j+1)B(n,j+2) + \frac{1}{3}B(n-1,j-3) -\sum_{p=1}^{n-1} B(n-p,j)B(p,1)$$ $B(n,j) = 0$ for $n=0$ or $j= 0$ or $(n<0)$ or $(j<0)$ $B(n,j)=0$, for $j>3n$ ...
0
votes
1answer
40 views

Need help with system of recurrence relations for computing the number of n-digit quaternary sequences

So my task is to find a system of recurrence relations for computing the number of $n$-digit quaternary sequences with: •An even number of $0$s •An even total number of $0$s and $1$s •...
0
votes
2answers
34 views

Find a recursive relation for the case of a length $n$ binary string where there are no three consecutive $0$'s.

Find a recursive formula for the following example. The number of binary strings of length $n$, such that there are no $3$ consecutive $0's$. I started by considering the length $n$ as a block ($1$ ...
1
vote
0answers
32 views

Is there an explicit formula for a integral recurrence relation (polynomials)?

Is there some general explicit solution to the equation $p_n(x)= k\int_{0}^{x} p_{n-1}(x-z) dx +b$, where $𝑝_0(x)=a$, and k, b, a and z are just constants. For x< z, $p_n(x)$ is "replaced" by a ...
0
votes
0answers
12 views

Recurrence Relation jumping forward and backwards between bounds of 0 and m

Question What I have gotten so far is as follows: $$q_{m,k} = q_{m,k-1}a_{n-1}$$ for $2|k$, otherwise it is $$q_{m,k} = q_{m,k-1} (m - a_{k-1})$$ Is there any way to make this into one recurrence ...
0
votes
2answers
15 views

Inhomogeneous Difference Equation $p_{n}+\frac{1}{4}p_{n-1}=\frac{3}{4}$ with $p_0=0, p_1=3/4$

I'm trying to solve the above equation, and this is where I've got to so far: Consider homogeneous problem $p_{n}+\frac{1}{4}p_{n-1}=0$. We then have characteristic equation $\omega^{n-1}(\omega + 1/...
0
votes
0answers
61 views

How do I solve $A_{n+2}-3A_{n+1}+A_{n}=n$ with $A_{0}=A_{1}=1$ using method of generating function?

$A_{n+2}-3A_{n+1}+A_{n}=n$ with $A_{0}=A_{1}=1$ using method of generating function I deducted the following formula: $$ F(x)= \frac{x^3}{(x-1)(2x-1)}-\frac{1}{x-1} \;, $$ where $F(x)= \sum_{n=0}^{\...
2
votes
1answer
23 views

What do first derivatives, factorials, and alternating signs have to do with explicit and recursive forms of sequences?

I'm a math teacher now, although a few years ago I was finishing up my M.Ed. As part of my studies, I was tasked with conducting my own study of high school level topics and finding unique results. As ...
0
votes
1answer
41 views

Is there an explicit formula for a integral recurrence relation (concerning polynomials)?

Is there some general explicit solution to the equation $p_n(x)= k\int_{0}^{x} p_{n-1}(x) dx +b$, where $p(0)=a$, and $k$, $b, a$ are just constants. I need this for a more specific example, but I ...
3
votes
2answers
46 views

Solving Recurrent Relations using Back tracking

The following formula has been provided: a(n) = a(n-1) + a(n-2) with initial states 0 , 2 After some research the formula is found to be a Binet's Formula. It is required to convert the ...
0
votes
1answer
19 views

how to prove this recurrence of determinants

the question is : Let Dn = $[a_{ij}]$n × n be a (n × n) determinant with the following conditions: $$a_{ij} = 4 ;i=j$$ $$a_{ij} = 2 ;|i-j|=1$$ $$a_{ij} = 0 ; otherwise$$ then we have to prove that : $$...
-2
votes
0answers
17 views

Questions based on interest rate

You borrow $18,000 to buy a car. The finance rate is 4% per year. You will make payments over 3 years. At the end of each month you will repay an amount b (in dollars), to be determined. Let an be the ...
1
vote
1answer
43 views

Lucas n-Step Starting Numbers?

I am very interested in n-Step Lucas numbers. Trying to find, the "true starting" values seem to be contentious? I would assume $(1,1), (1,1,1), (1,1,1,1)$; like Fibonacci. However, 2-Step Lucas is $(...
0
votes
0answers
10 views

Transform two recursively defined polynomial sequences to eqach other by transforming depending variable

Lets define the two recursive polynomial sequences by \begin{align} A_0(x) &= 1 \\ A_n(x) &= x \sum\limits_{k=1}^{n} k \cdot A_{n-k}(x) \end{align} and \begin{align} B_0(y) &= 1 \\ B_n(...
0
votes
1answer
17 views

Transformation of recursive defined polynomial to reverse coefficient order?

Lets define a recursive polynomial sequence by \begin{align} A_0(x) &= 1 \\ A_n(x) &= x \sum\limits_{k=1}^{n} k \cdot A_{n-k}(x) = \sum\limits_{k=1}^n a_k x^k \end{align} Is there a way to ...
1
vote
1answer
32 views

Help with a specific recurrence relation? [closed]

Can anyone help me find an exact formula for $a(n)$ here-? I have tried this many times but did not arrive at a neat answer. $(4n-2)a(n) = a(n-1) + \frac{2(4n-1)}{4^n(n-1)!}$ $a(1) = \frac{3}{4}$
0
votes
1answer
21 views

Solving a non-linear recurrence relation with binomial coefficient

I'm trying to solve a recurrence relation $\displaystyle \sum_{i=0}^{n}\binom{n}{i}\frac{A_i}{(n-i+1)}=0$, where $A_0=1$ first few terms are $A_1=-\frac{1}{2}$, $A_2=\frac{1}{6}$, $A_3=0$, $A_4=-\...
3
votes
2answers
53 views

Solve the following recurrence relation

Given that $$a_{n+1}=(r+1)a_n-ra_{n-1}$$ where $r$ is a known parameter, I have to find an expression for $a_n$ knowing that $a_0=0$, $a_T=1$ (where $T$ is also a known parameter).
1
vote
1answer
69 views

Recurrence relation for the partial sum of an alternating series

If $z \in \mathbb{Z}^+$ and $p_{z,n}$ is the number of sequences, $a_1, \dots, a_n$ of size $n$ where $a_i \in \mathbb{Z}^+$, so that for $0 \leq j \leq n$: $$0 \leq \sum_{i=1}^j (-1)^{i-1}a_i \leq z$$...
2
votes
2answers
31 views

Finding the general formula for the sequence with $d_0=1$, $d_1=-1$, and $d_k=4 d_{k-2}$

Suppose that we want to find a general formula for the terms of the sequence $$d_k=4 d_{k-2}, \text{ where } d_0=1 \text{ and } d_1=-1$$ I have done the following: \begin{align*}d_k=4d_{k-2}&...
0
votes
0answers
20 views

How can I find the complexity of this recurrence?

I've to solve the following recurrence: $T(n) = 2T(n-1) - 1$, for $n \geq 1$ $T(n) = 1$, for $n = 0$ I'd easily proved that $T(n) = O(2^n)$, however it seems that $T(n)$ is $O(1)$ actually. So, ...
0
votes
1answer
19 views

Recurrence equation process of solving

i am solving some reccurence relations and I am getting lost and not sure where to go I have $$T(n)=T(n-1)+ 1/7^{(n-1)}\quad \text{ where } T(1)=1$$ Which I tried solving with something like this <...
0
votes
2answers
52 views

Do we solve the recurrence relations by expanding the terms?

Solve the following recurrence relation: $a_k=2 a_{k-1}+3a_{k-2}$ with $a_0=1$ and $a_1=2$. I have expanded the recurrence relation: $$a_k=2 (2 a_{k-2}+3 a_{k-3})+ 3(2 a_{k-3}+3 a_{k-4})= 2^2 a_{k-...
2
votes
3answers
66 views

Recurrence relation $a_{n+1}=a_n^2-2$

Sequence $a_n$ is defined $a_{n+1}=a_n^2-2, a_0=\alpha$. I know that a closed form for $a_n$ is $a_n=\beta^{2^n}+\frac{1}{\beta^{2^n}}$, where $\beta$ satisfies $\beta+\frac{1}{\beta}=\alpha$ and I ...
0
votes
1answer
23 views

Number of full binary trees is Catalan, What is the number of Binary trees?

In exercise 12-4 of "Introduction to Algorithms" by Cormen et.al (third edition), they mention that the number of Binary trees with $n$ nodes is given by the Catalan numbers, $$b_n = \frac{1}{n+1}{2n ...
0
votes
0answers
40 views

A permutation π on $[n]$ is said to be even-dominated if $\phi_{2i−1}< \phi_{2i}> \phi_{2i+1} \ for \ all 1 ≤ i < n/2 $

Let a be the number of even-dominated permutations on $[n]$. Let $a(x)$ be the exponential generating the function of $(a_n)_{n≥0}$.
1
vote
1answer
44 views

Driving the state of a discrete system to zero in one step

I have the following system of difference equations: $\textbf{x}(k+1) = A \textbf{x}(k) + \textbf{b} u(k)$ where: $A = \begin{bmatrix} 1 & 2 \\ 3 & \alpha \end{bmatrix} $ and, $\mathbf{b} =...
1
vote
2answers
65 views

Why is $\prod_{n}^{n-1} = 1$ and $\sum_{k=j+1}^{j}=0$?

The general first-order difference equation has the form $$ x_{n+1}= a_n x_n + g_n, \quad n\geq 0, \tag 1 $$ where $(a_n)_{n\in \mathbb N_0}$ and $(g_n)_{n\in \mathbb N_0}$ are given sequences. ...
0
votes
1answer
19 views

“Plus and minus filling” problem

Let's say that we want to fill n squares each lying on one line, with plus'es, minus'es, or zero's in such a way that plus never lies next to minus. The question is - in how many ways can we fill ...
0
votes
1answer
8 views

Linear Non-homogeneous Recursive Relation

this is the problem: $f(n) = 4f(n-1)-3f(n-2)+2^n+n+3$ where $f(0)=1 , f(1)=4$ I know when the Non-homogeneous part is a product of an exponential function and a polynomial function like this: $S^n(...
0
votes
0answers
7 views

Relation between Leslie dinamical system matrix and homogeneous 3rd degree recurrence relation

For a simple Leslie Matrix and asociated system we can get the value of a vector $x_0$ by using $X_{n+1}=AX_N$. For example with the following system $X_{N+1}=AX_N=\begin{pmatrix} 0 & 3 & 5\\ ...
0
votes
0answers
45 views

Reduction Formulae of $I_n=\int_0^\frac{\pi}{4}\tan^nx\, dx$ and $J_n=(-1)^nI_{2n}$

Let $I_n=\int_0^\frac{\pi}{4}\tan^nx\,dx$ and let $J_n=(-1)^nI_{2n}$ for $n=0,1,2$ Show that $I_n+I_{n+2}=\frac{1}{n+1}$. Deduce that $J_n-J_{n-1}=\frac{(-1)^n}{2n-1}$ for $n\ge1$ Show that $J_m=\...
1
vote
1answer
49 views

Show if $x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$, then $1\le x_n \le 2$ for all $n\in\mathbb{N}$ using Strong Induction

Let $x_1=1$, $x_2=2$, and $x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$. Show using strong induction that $x_n\in [1,2]$ for all natural $n$. So I know just from inequalities that if $a<b$ then $a<\frac{...

1
2 3 4 5
140