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

learn more… | top users | synonyms (2)

0
votes
0answers
67 views

Counting all permutations(repeating) with no adjacent elements equal and m majority elements.

Counting all permutations(repeating) of 1 to n which have size n. 1. with no adjacent elements equal, and 2. m majority elements(A element is majority element when it appears max number of times in ...
27
votes
0answers
850 views

This one weird thing that bugs me about summation and the like

Most of us know $$\sum_{n=a}^b c_n=c_a+c_{a+1}...+c_{b-1}+c_b$$ Some of us know $$\prod_{n=a}^b c_n=c_a \cdot c_{a+1}...c_{b-1} \cdot c_{b}$$ A few of us know ...
0
votes
2answers
90 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
0
votes
1answer
30 views

Proving merge sort is $O(n^2)$ using induction

I'm trying to show that merge sort is $O(n^2)$ using induction. (I'm just concerned with powers of two for simplicity). However, I'm stuck at the last inequality Basis step: Show that there exists a ...
1
vote
0answers
21 views

Recursive definition of sequences inverse/equivalency.

So here's the problem: "Give a recursive definition of the sequence ($a_n$), $n = 1, 2, 3, ...$ if $a_n = 4n - 2$." Here's my answer:$$t_1 = 2; t_n = t_{n-1} + 4$$ However, I know this could also ...
0
votes
1answer
52 views

how to solve $ T(n) = T (2n/3) + 1$ using master theorem?

I solved the above recurrence using master theorem and applied case $2$ to solve it. However in the final answer I have $T(n) = \Theta(\log^{(k+1)} n)$ . what should happen to $k+1$? because the ...
0
votes
0answers
14 views

Complexity of recurrence containing geometic series.

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
2answers
36 views

Complexity of recursive algorithm.

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
1
vote
1answer
41 views

How to solve recurrence relation $T(n)=T(n-1)+\lceil \log(n) \rceil$

Without the ceilings, the solution is reasonable clear (given here). Is there a way to reach a solution with the ceilings, or the difference between the two?
1
vote
1answer
32 views

$T(n) = 4T(n/3) + n\log_3(n)$ using Mater Theorem?

I am trying to solve this recurrence using the Master Theorem. $$T(n)=4T(n/3)+n\log_3n.$$ I tried this: We have: $a=4$, $b=3$ and $f(n)=n\log_3n$. I think that $f(n)$ is $O(n^{\log_ba - ...
2
votes
0answers
35 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
0
votes
1answer
27 views

Recurrence in Kepler's Equation (trascendent equation)

Kepler's equation is $E-e\sin E = M$, where $e,M$ are constants. My teacher of celestial mechanics told me that if $e\ll 1$, I should take a first aproximation $E_1=M$, then a second aproximation ...
1
vote
1answer
34 views

recurence equation: $(\lambda + \gamma) f_n = \gamma (1-p)^{n-1} f_{n+1} + \gamma [1-(1-p)^{n-1}] f_{n+2} + \lambda f_{n-1}$

I am trying to analytically solve the following recurrence equation $(\lambda + \gamma) f_n = \gamma (1-p)^{n-1} f_{n+1} + \gamma [1-(1-p)^{n-1}] f_{n+2} + \lambda f_{n-1}\,,$ Under constraints of ...
4
votes
2answers
149 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
34 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
94 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
85 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
23 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, ...
5
votes
1answer
172 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
24 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
251 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
49 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
29 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
117 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
66 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
38 views

Calculating Running Time of Recurrence Relations

I had to calculate the Running Time of the following Algorithm. ...
1
vote
2answers
51 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
135 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} - ...
3
votes
4answers
175 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
31 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
22 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
60 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
70 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
43 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
49 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
39 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
56 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
86 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
30 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
20 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
15 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
20 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
27 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
36 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
31 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
26 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
73 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
18 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 ...