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

learn more… | top users | synonyms (2)

0
votes
2answers
38 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
1
vote
1answer
48 views

Can reduction formula be applied on $\int \cos^n x \: dx$ when n is a negative integer?

The reduction formula states as: enter image description here for integration of $\cos^n x$: $$ \int \cos^n x \: dx=\frac1n \cos^{n-1} x\sin x+\frac{n-1}n \int \cos^{n-2} x \: dx $$ But if ...
0
votes
1answer
62 views

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix…

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix. Solve this recurrence relation for an expression of the number of off diagonal entries as a ...
0
votes
0answers
21 views

What to do if your characteristic equation is not fully reducible over your field when solving a recurrence relation?

My problem is a little more difficult. However, essentially, my problem comes up when we're supposed to find the solution to: $R(n)=R(n-3)+1$, $R(0)=R(1)=R(2)=1$ (the initial conditions don't matter ...
0
votes
1answer
24 views

Solve Non-homogeneous recurrence relations

Solve the recurrence relation $u_n = 2u_{n-1} + 2^n - 1$ where n is greater than or equal to 1 and $u_0=0$. We have characteristic root equal to 2 with multiplicity 1. So homogeneous part will have ...
0
votes
1answer
31 views

How I can solve this difference equation: $(2m+3) w_{m}-(2m+1) w_{m+1}-2m²-4m-1=0$

How I can solve this difference equation: $$(2m+3) w_{m}-(2m+1) w_{m+1}-2m²-4m-1=0$$ I have no idea to start.
0
votes
1answer
40 views

Showing that $x_n=nx^n$ is a solution of the recurrence relation

Given that $r^2 - ar - b$ has the double root $x$, how do you show that $x_n = nx^n$ is a solution of $x_{n+1}=-4x_n-4x_{n-1}$? I can show $x_n$ = $x^n$ but I just can't show for $x_n$ = $nx^n$.
0
votes
1answer
27 views

Nth term of the sequence satisfying this recurrence relation?

How do you find a formula for the nth term of the sequence that satisfies: $x_n$$_+$$_1$=$-4x_n$-$4x_n$$_-$$_1$? $x_0 = 1$, $x_1 = 0$ I substituted $x_n$ = $x^n$ then found that the roots of the ...
0
votes
2answers
44 views

find a recurrence relation for the sequence

Let $a_n$ be the number of words of length $n$ containing only letters “X” and “Y” without two consecutive “Y”. For example, $a_3 = 5$ since there are exactly five such words: $$\mathrm{XXX, XXY, XYX, ...
0
votes
2answers
80 views

How to find range of values for which a sequence converges?

Say you had the sequence $U_{n+1} = 2bU_n$ where $U_1 = 6$. How would you find the range of values of b for which the sequence converges?
1
vote
0answers
31 views

Closed form of a recurrence relation

I was given this problem: Given a set of $n$ elements, how many possible involutions can we form? I have managed to device this recurrence relation: $$t_n=t_{n-1}+(n-1)t_{n-2}$$ How can I form a ...
0
votes
1answer
101 views

Derive recurrence relation for Chebyshev polynomials from generating function

Hej, I have a question about the following problem: Derive a recurrence formula for $m \ge 0$ given the generating function formula $$ \frac{1}{1-2xt+t^{2}}=\sum_{m=0}^\infty U_m(x)t^{m}. $$ What I ...
3
votes
2answers
106 views

Setting up a recurrence relation of ternary strings of length n that does not have three consecutive 1s

Let $a_n$ denote " the number of ternary strings of length n that do not contain three consecutive 1s" Ternary string contains only 0, 1, 2 and has length n. The way I approached it was to make a ...
3
votes
1answer
56 views

Fibonacci-Like Sequence: Breeding Rabbits

I came across the following question on a math test: Suppose Fibonacci's research in the breeding habits of rabbits has been adjusted. They are now believed to be fertile after $2$ months of life, ...
0
votes
1answer
125 views

Determining the recurrence relation

I am having trouble with this problem. I am trying to see if I am doing this properly, and it would be very helpful if someone could check my work. Here is the problem: A piece of paper is 1 inch ...
0
votes
1answer
36 views

How to find a large $U_n$ from a recurrence formula.

I am studying sequences as part of A-Level Maths and we are doing the recurrence formula type questions. Say it is $u_{n+1} = u_n - u_{n-1}$. And you were asked to find the values of $u_{13}, ...
1
vote
1answer
31 views

How to give a recursive definition and a direct formula and prove that they both are equivalent.

How to give a recursive definition and a direct formula and prove that they both are equivalent. for example, 10,13,16,19,22,25 I know the formula for this is a,a+d,a+2d,a+3d,... ...
0
votes
4answers
60 views

Find the general formula for the sequences

1=1 2+3+4+=1+8 5+6+7+8+9=8+27 10+11+12+13+14+15+16=27+64 Find the formula is suggested by these equations?Prove your answer is correct. I saw this question on practice exam and ...
0
votes
1answer
40 views

given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...
1
vote
1answer
18 views

Combinatorics partitioning problem: find $\sum_{n\geq 0} a_{n,k}\frac{x^n}{n!}$

'If $a_{k,n}:=$ the number of ways of partitioning $n$ distinct objects into $k$ odd parts, what is $F_k(x)=\sum_{n\geq 0} a_{n,k}\frac{x^n}{n!}=?$' If I understand correctly, $a_{k,n}$ is the $n$th ...
0
votes
3answers
43 views

How to prove that $\det(Z_{n}) = \det(Z_{n-1}) - \det(Z_{n-2})$?

I'm given an $n \times n$ matrix $Z_{n}$ over $\mathbb{N}$ of which the entry in the $x$-th row and the $y$-th column equals 1 if $|x-y| < 1 $ or $ |x-y| = 1$ and zero otherwise. I'm trying to ...
-4
votes
2answers
137 views

Recurrence Relations, calculating [closed]

http://puu.sh/lEJIB/941352c776.png How do you calculate u2 and u3? u2 = 2(2)-3, u3 = 2(3)-3?
4
votes
1answer
179 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
1
vote
6answers
100 views

Closed form of $\sum_{k=0}^{n}k\cdot2^{n-k}$

I am interested in solving the recurrence relation using iterative method. I know how to solve it using generating function and another method using solution of associated linear homogeneous ...
2
votes
0answers
27 views

Solving recursions with max

The question is general, but I'll first give a simple example. Suppose you have a candy machine with $N$ candies. The machine is weird, when you give it a quarter it gives you $1$ to $N$ candies (all ...
1
vote
2answers
35 views

Constructing a recurrence relation regarding binary sequences

For each positive integer $n$, let $a_n$ be the number of binary sequences of length $n$ which do not contain the subsequence $011$. Construct a recurrence relation for $a_n$. My attempt: Initial ...
1
vote
0answers
49 views

Why is the Taylor series of $1/\sqrt{1-4q^2}$ popping up in my recursively defined triangle of polynomials?

While answering this question I stumbled on some nice (inexplicable) observation where a recursively defined sequence of polynomials turned out to coincide with some Taylor development I'll start ...
0
votes
0answers
22 views

Solving a non homogeneous recurrence relation

If we have a recurrence relation like $a_n$ = $a_{n-1} + 5 $ with $a_0=30$, can this be solved using finding characteristic roots and then characteristic roots, I can solve other type of such ...
0
votes
2answers
47 views

Can I solve this recurrence relation with characteristic polynomials

Solve the following recurrence relations subject to the initial condition: $$a_{n}=2a_{n-1}+2^n, a_{1}=1$$ I have successfully solved this problem via telescoping, however I would like ...
2
votes
0answers
27 views

Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
0
votes
2answers
31 views

How to solve the recurrence $a_n = -2n a_{n-1} + 3n(n - 1) a_{n-2}$

I have problems with solving recurrences using changing variables, The recurrence relation is: $a_n = -2n a_{n-1} + 3n(n - 1) a_{n-2}$ $a_0 = 1$ $a_1 = 2$ The solution in my book is as follows ...
0
votes
1answer
58 views

Combinatorics - Recurrence relation

For each positive integer $n$, let $a_{n}$ be the number of binary sequences of length $n$ which do not contain the sub-sequence '011'. Find a recurrence relation for $a_{n}$ and determine the initial ...
3
votes
2answers
51 views

How do I find $\liminf$ and $\limsup$ if $a_{2n}=\frac {a_{2n-1}}2$ and $a_{2n+1}=\frac12+\frac {a_{2n}}2$?

Its given that $a_1=a>0$ and that for any $n>1$ two things happen: $$a_{2n}=\frac {a_{2n-1}}2$$ $$a_{2n+1}=\frac12+\frac {a_{2n}}2$$ How do I find $\lim\inf$ and $\lim\sup$ I am trying to look ...
1
vote
0answers
16 views

nodes equation cant find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level N where $X$ is located to narrow our ...
0
votes
2answers
39 views

Solving quadratic recurrence inequality

Let $(n_k)$ be a sequence of natural numbers starting at $n_1=2$ and growing as follows $$n_k\leq n_{k+1}\leq n_k^2+2$$ As far as I know this sort of dynamical system may have no closed-form solution, ...
0
votes
2answers
23 views

Closed form expression for zero of recurrence relation

Given the recurrence $d(i+1)=xFib(2i+1)-nFib(2i)$, where $Fib$ denotes the Fibonacci sequence (i.e. $Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2$, etc) and $n$ and $x$ are arbitrary integers, is it ...
2
votes
1answer
217 views

Number of ways to pair off $2n$ points such that no chords intersect

For $n \geq 0$ evenly distribute $2n$ points on the circumference of a circle, and label these point cyclically with the numbers $1, 2 . . . , 2n$ Let $h_n$ be the number of ways in which these $2n$ ...
0
votes
0answers
20 views

How to prove the independence of the general solution of an arbitrary homogeneous linear recurrence equation with constant coefficients?

Given the equation $y_{n+k}+a_{k-1}y_{n+k-1}+\cdots + a_0y_n=0$ with $a_o,\cdots,a_{k-1} $ constants, I know that the solution has the form: $y_n=n^{j}\lambda_i^{n}$ with $j=0,1,\cdots k_i-1$ where ...
0
votes
1answer
20 views

How to start dealing with this recurrence relation

I have never seen a recurrence in this form, so I don't know how to proceed. I'm supposed to find asymptotic bounds (preferably $\Theta$(something)) for: $$T(n) =T\bigg(\frac{n}{\log n}\bigg)+ \log ...
1
vote
1answer
40 views

generating functions (reccurence relations)

how can I use generating functions to solve the reccurence relation $$a_n = 4a_{n-1} -4a_{n-2}$$ $$a_1 = 1, a_2=3$$ some terms: 1,3,8,20,48 $$a_n -4a_{n-1} +4a_{n+2} =0$$ ...
0
votes
1answer
74 views

How to make the imaginary number disappear?

I am trying to solve one recurrence relation $a_n - 2a_{n-1} + 2a_{n-2} = 0, a_0 =1, a_1 = 2$ Now I was able to get the characteristic equation $r^2 -2r + 2 = 0$ , I get that $r=1 \pm i$ and ...
1
vote
1answer
32 views

Recurrence relations and eliminating the complex numbers

I want to solve the following recurrence relation, But I can't get rid of the complex numbers appearing. $a_n - 2a_{n-1} + 2a_{n-2} = 0, a_0 =1, a_1 = 2$ First, I let $a_n = cr^n$, then I find ...
1
vote
1answer
36 views

Solving a recurrence relation without the characteristic equations

I am new to solving recurrence relations and I am presented with the following two problems (1) $$a_n = (3n-1)a_{n-1}, a_0 = 3$$ and (2) $$a_{n+3}-6a_{n+2} + 11a_{n+1}-6a_{n} = 0, a_0 =1, a_1 =1, ...
0
votes
0answers
29 views

Ladder (recurrence) operators for Hermite polynomials?

Generally, Hermite polynomials can be described using the Rodrigues formula: $$ H_n(x) = (-1)^n e^{x^2}\frac{d^n}{dx^n}e^{-x^2} $$ And the first few polynomials (for $n = 0,1,2,3,4,5...$) are well ...
1
vote
4answers
72 views

Solving $a_n=3a_{n-1}-2a_{n-2}+3$ for $a_0=a_1=1$

I'm trying to solve the recurrence $a_n=3a_{n-1}-2a_{n-2}+3$ for $a_0=a_1=1$. First I solved for the homogeneous equation $a_n=3a_{n-1}-2a_{n-2}$ and got $\alpha 1^n+\beta 2^n=a_n^h$. Solving this ...
0
votes
1answer
33 views

Fibonacci sequence emerging from integer partitioning

Let $a_n$ count the number of ways a sequence of $1$s and $2$s will sum to n. For example $a_3 = 3$ since $1 + 1 + 1 = 3 = 1 + 2 = 3 = 2 + 1 = 3$ (The ordering matters so 1 + 2 is different from ...
3
votes
2answers
89 views

Convergence of the sequence $a_{n+1}=\frac{a_n^2(a_n-3)}{4}, a_0=-\frac12$

I approached the problem as follows. First, note that if $a_n<0$ then $a_{n+1}<0$. Since $a_0<0$, it follows that the sequence is bounded above by zero. Now, consider the difference ...
0
votes
0answers
14 views

Expectational Difference Equation

I am having trouble with the following difference equation: $$ y_t = \sum_{j=0}^\infty b^j E_t x_{t+j},\, 0<b<1 $$ where: $$ \Delta x_t = \phi \Delta x_{t-1} + \varepsilon_t $$ I would like ...
2
votes
0answers
41 views

Solving the recurrence relation $a_k=3a_{k-1}+4a_{k-2}$ with $a_0=1$, $a_1=2$

Solve the recurrence relation $a_k=3a_{k-1}+4a_{k-2}$ with $a_0=1$, $a_1=2$ using characteristic equation. These are the steps I used. Is my work correct?
2
votes
2answers
40 views

Finding a closed form solution for a recurrence

You open an account at a bank that pays 5% interest yearly, and deposit $a_0$ dollars in it. Every year you withdraw 10 times the number of years you have had the account. For example, if you started ...