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

learn more… | top users | synonyms (2)

4
votes
2answers
99 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
0
votes
0answers
16 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
1
vote
2answers
61 views

Solving 2nd order linear recurrence with non-constant coefficients

I am trying to find a general solution to the following definite integral: $$F_{n}{\left(a,b;z\right)}:=\int_{a}^{z}\frac{x^{n}}{\sqrt{\left(x-a\right)\left(b-x\right)}}\,\mathrm{d}x,\tag{1}$$ ...
1
vote
2answers
66 views

Solution of recursive polynomial functions

Is there anything that can be said about the roots of the polynomial $f_n(x)$ if $f_n(x) = xf_{n-1}(x) + f_{n-2}(x)$ where these are polynomials of degree $n, n-1,$ and $n-2$, respectively? My goal is ...
0
votes
0answers
12 views

Pyramidal TSP without weight

Say $G=(V,E)$ with $V=\{1,...n\}$ and $l(i,j)$ is the distance of arc $(i,j) \in E$. The aim is to find a pyramidal path in $V$ with minimal length. A pyramidal path is a sequence of vertices $(n,i_1, ...
4
votes
1answer
139 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
0
votes
1answer
19 views

Markov-Chain with general state space - recurrent sets

I have an irreducible Markov Chain $(z_n )_{n\in \mathbb N } $ with state space $X$ and with transition-probability-kernel $K$, so $K(x,\cdot)$ is a probability measure (on the $\sigma$-Algebra ...
0
votes
2answers
22 views

How to make clear sense of this re-write of an equation

I'm having a little trouble intuitively seeing the step being performed here. $2\times(2\times(2\times(2\times(2\times3+3)+3)+3)+3)+3) = 2^5\times3 + 2^4\times3 + 2^3\times3 + 2^2\times3 + ...
1
vote
2answers
83 views

Finding a recurrence relation, first few terms of power series solution to differential equation

I'm attempting to find a recurrence relation and the first few terms of a power series solution for the differential equation: $$(1-x^2)y \prime\prime - 2xy\prime + \lambda y = 0$$ Where $\lambda$ ...
1
vote
1answer
36 views

General solution of $(1-x^2)y''-2y=0$ about $x_0=0$?

I've expanded this differential equation as a series to obtain the recurrence relation $$a_{n+2}=\frac{a_n(n^2-n+2)}{n^2+3n+2}.$$ I don't know how to find $a_n$ in terms of $a_0$ and $a_1$ so that I ...
1
vote
0answers
19 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
1
vote
1answer
23 views

Does a terminating recurrence relation diverge?

Given the recurrence relation $$u_1=-3.25 \ \& \ u_{k+1}=\frac{4}{u_k+2}$$ is $\{u_k\}$ convergent? A quick check for the definition of convergence gives the following: If $\forall \epsilon \ ...
2
votes
2answers
78 views

Challenging integral

I am trying to find a close form representation for the following integral: $$ A(x;a,b,c)= \int_{0}^{x}\frac{\sin\left(a k+b k^{2}\right)+\sin\left(c k-b k^{2}\right)}{k}dk $$ for $0<x \ll ...
2
votes
1answer
37 views

Counting Inversions - Recursive Algorithm

Now in my lecture notes in a course I'm taking I was given the following pseudo-code to Count Inversions (Using a Recursive Algorithm). ...
0
votes
2answers
30 views

Calculating Running Time of Recurrence Relations

I had to calculate the Running Time of the following Algorithm. ...
1
vote
2answers
48 views

Prove the following recurrence: $F_{2n+1}=3F_{2n-1}-F_{2n-3}$

Prove the following identity: $$F_{2n+1}=3F_{2n-1}-F_{2n-3}$$ So far I know that $F_n=F_{n-1}-F_{n-2}\implies F_{2n+1}=F_{2n}+F_{2n-1}$ Just not sure where to go from here to get to the conclusion. ...
0
votes
1answer
126 views

Derive a 2D recurrence from a set of linear recurrences

Given a set of high-order linear recurrences: $A(1, n): 0, 1, 0, 1, 0, ...$ $A(2, n): a_{n} = 2a_{n-2} - a_{n-4}$ $A(3, n): b_{n} = 3b_{n-2} - 3b_{n-4} + b_{n-6}$ $A(4, n): c_{n} = 4c_{n-2} - ...
2
votes
4answers
154 views

Recurrence relation for right-angled triangles stuck-together

Given the image: and that $x_0 = 1, y_0=0$ and $\text{angles} \space θ_i , i = 1, 2, 3, · · ·$ can be arbitrarily picked. How can I derive a recurrence relationship for $x_{n+1}$ and $x_n$? I ...
0
votes
0answers
30 views

How to compute linear recurrence of a sum of binomial-multiplied linear recurrences [duplicate]

I have $$g(n) = \sum_{k=1}^{n} \binom{n}{k}f(k)$$ where $f(k)$ is a large linear recurrence. $g(n)$ is also a linear recurrence as well. Normally, when computing the value of a linear recurrence, I ...
1
vote
1answer
17 views

Problem with nonhomogeneous recurrence relations

I studying Discrete maths during this semester and I need your help. I have been trying to solve one non-homogeneous recurrence relation and read many-many guides how to do this, but I haven't found ...
4
votes
1answer
53 views

Simplying linear recurrence sum with binomials

Is there a way to simplify $$\sum_{k=1}^{n} \binom{n}{k}f(k)$$ Where $f(k)$ is a large linear recurrence?
4
votes
1answer
62 views

Dynamical system $x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,…$

Consider the dynamical system $$ x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,... $$ So by using the substitution $x_n = \cot(y_n)$, I have found: $$ x_n = \cot(\cot^{-1} ...
1
vote
1answer
42 views

Solving Log equation using master theorem

I`m studying Master Theorem, and I got stuck in the case 3. The example is : T(n) = 3T(n/4) + nlogn. I have no idea how my teacher got the final value, c = 3/4, based on the equation below : 3*[n/4 ...
0
votes
2answers
39 views

Solve the following recurence relation.

While I was working on some graph theory problem I encounter the following recurrence relation $$a_{n+1}=a_{n-1}+6$$ where $a_0=3.$ Note: I have rewritten the recurrence relation as recommended.
0
votes
1answer
37 views

Recurrence relation of $T(n) = T(n^\frac13) + \log n$

I'm having trouble deciphering what this recurrence relation is: $$T(n) = T(n^\frac13) + \log n$$ when I try to expand it out I get: $T(n) = T(n^\frac1{3^k}) + k\times\log n $ my problem is ...
1
vote
2answers
43 views

Solve recurrence relation - t(n)=(n-1)*t(n-1) [closed]

How can I solve the following recursive relation: t(n)=(n-1)*t(n-1) where the base case is t(1)=1 Is it okay just saying ...
2
votes
2answers
71 views

Proving an expression is perfect square

I have this expression I got in one larger exercise: $$\frac{(2+\sqrt3)^{2n+1}+(2-\sqrt3)^{2n+1}-4}{6}\frac{(2+\sqrt3)^{2(n+1)+1}+(2-\sqrt3)^{2(n+1)+1}-4}{6}+1$$ and i need to prove it is perfect ...
0
votes
2answers
28 views

Sequence of numbers recurrence relation

A sequence of real numbers $$ u_1, u_2, u_3... $$ satisfies $$u_1=1$$ and the recurrence relation $$4u_{n+1}=au_n-2$$ for all positive integers n where a is a real constant. Express $$u_n$$ in terrms ...
1
vote
1answer
18 views

How can I find the sum of any homogenous linear recurrence relation?

I've become interested in linear recurrence relations of the form $a_n=-a_{n-1}-a_{n-2}- ... $ where $a_0=1$. For the first of these relations I considered $a_n=-a_{n-1}-a_{n-2}$ where $a_0=1$ and ...
0
votes
1answer
12 views

Reccurence for the numbers of the strip partition

Let's consider a partition of a strip $ 3 \times n$ into $1 \times 2$ rectangles and call $a_{n}$ - the number of such partitions. For instance, $a_{0}=1, a_{1}=0, a_{2}=3, a_{3}=0 \ldots$. How to ...
1
vote
0answers
16 views

Recurring Folds Through A Circle

If I were to cut a circular disk of paper, I would have a disk with one section. If I were then to fold it through its centre, I would have a disk with two sections (divided by the crease). If I were ...
1
vote
1answer
20 views

How to solve the delay algebraic equation $xf(x) + \alpha f(x - {x_0}) - \alpha f(x + {x_0}) = 0$?

In the process of solving a problem, I am faced with the problem of finding a non-zero function $f:\mathbb{R} \to \mathbb{R}$ which satisfies the equation $$xf(x) + \alpha f(x - {x_0}) - \alpha f(x + ...
1
vote
1answer
32 views

Closed form of recurrence equation

I am solving warm up problem 1.2 from Concrete Mathematics book. I've got the right answer by induction: $$ f(0) = 0\\ f(n) = 3f(n-1) + 2, $$ But I can not figure how to simplify it to the closed ...
0
votes
2answers
30 views

Prove that two recursive sequences are always not zero.

I have the following recursive sequences: $x_n = x_{n-1} + 2y_{n-1} , x_1 = 1$ $y_n = y_{n-1} - x_{n-1}, y_1 = -1$ where $ x_n,y_n \in \mathbb{Z}$ I have to show that for any $n$ neither $x_n$ ...
0
votes
0answers
20 views

Solving a linear recurrence with a multiplicity of two

I was given this problem and I am trying to figure out where I go wrong solve the linear recurrence: $f(0) = 0$, $f(1) = 0$, $f(2) = 18$, $f(n) = 3f(n − 1) − 4f(n − 3)$ Here is what I have so ...
0
votes
1answer
61 views

Find a function F(n) that satisfies the recurrence

i am stuck with this problem Find a function F(n) that satisfies the recurrence F(n) = 2F(sqrt(n)) + 1 for all n ∈ N Please help me...
0
votes
1answer
17 views

Recurrence Relation with Strings

Q. How many strings in {0,1,2,3} have an even number of 1's. The answer provided uses the recurrence relation $a_{n+1} = 3a_n + (4^n - a_n)$. The hint given was that consider the last string of ...
9
votes
2answers
271 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color ...
0
votes
3answers
71 views

Calculus: Converge of a recursive series?

I'm going crazy to solve this problem: I've a sequence defined by: $$x_1 = 1$$ $$x_2 = 2$$ $$x_{n+2} = \frac{1}{2}(x_{n}+x_{n+1})$$ And I have to prove that this sequence converges and what is its ...
-1
votes
1answer
64 views

Result of a $2D$ random walk after $n$ steps

One of my friends(who is around $8$ years bigger) gave me the following question:- A man is initially at the origin and can move in a line parallel to the X and Y-axis only. Given that the man takes ...
1
vote
1answer
41 views

How can find this two sequence recursive relations?

Let $$D_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j-1},E_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j}$$ I want find $D_{n}$ and $E_{n}$ recursive relations, I ...
1
vote
2answers
26 views

Simplification of an Equation with Recurrence Relations

I'm reading through examples on this site. In example 2_2, given the recurrence relation $A_n - 2A_{n-1} = 2n^2$, the guess for the particular solution is $A_n= Bn^2 + Cn + D$. Substituting that into ...
2
votes
0answers
44 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
1
vote
1answer
17 views

Inequality for recursive-defined values

$f_{n+2} = \frac{6}{5}f_{n+1}-f_{n}, f_0 = 0, f_1 = 1$ I need to prove that $f_n < 5/4$ I found that $f_{n} = \frac{1}{8} i 5^{1-n} \left((3-4 i)^n-(3+4 i)^n\right)$ and spend much time for ...
0
votes
1answer
31 views

I do not understand Recurrence Examples on donald knuth's concrete mathematics last page on chapter 1 [closed]

Example 1: When $n = 100 = (1100100)_2$ our original josephus values $\alpha=1,\beta=-1,\gamma=1$ yield: Answer: $ n = \qquad(1\qquad 1\qquad 0\qquad 0\qquad 1 \qquad 0\qquad 0)_2\quad=\quad 100\\ ...
0
votes
2answers
117 views

Sequences of sums of Pascal's triangle

The sequence $$ 1,3,6,10,16,28,56,120,256,528,1056 $$ is defined in OEIS as "sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 2"". It satisfies the recurrence $$ a(n) = ...
-2
votes
1answer
76 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?
1
vote
2answers
34 views

Solving a recurrence relation (textbook question)

$a_{n+1} - a_n = 3n^2 - n$ ;$a_0=3$ I need help for solving the particular solution. Based on a chart in my textbook if you get $n^2$ the particular solution would be $A_2n^2 + A_1n + A_0$ and $n$ ...
0
votes
0answers
31 views

Does this problem have analytic/approximate analytic solution?

Define $F[i]=F[i-1]-F[i-1]^c$ with $F[0]=r>0,c\in(0,1)$. Define $R(r,c)=\min\{i:F[i]<1\}$. What is solution to $c\in(0,1)$ in $R(r,c)=r^{1/k}$ with some given $k>1$?
0
votes
0answers
19 views

Riccati Finite Difference Equation:

Question: Consider the finite difference equation in Zeilberger notation: $$D_{1,x} [y] = a_0(x) + a_1 (x) y + a_2 (x)y^2 $$ Which in functional form is: $$ y(x+1) - y(x) = a_0(x) + a_1 (x) y + ...