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

learn more… | top users | synonyms (2)

1
vote
1answer
73 views

forming difference equation

there is a square with $60$ equal blocks. If a mosquito(bug)is set to fly starting at block $1$, it is equally likely to fly to other blocks. what is the probability after $n$ flies, the mosquito is ...
1
vote
1answer
53 views

How to convert this equation into a matrix form

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$ where $F(x)=1$ if $x<k$. $a,b,c,k$ are known (and positive) and $x$ is chosen. I want to solve this recurrence using a matrix but don't really know how to ...
1
vote
1answer
136 views

Solving Recurrence Relation by Generating Function Method

Im trying to solve an-7a(n-1)+10a(n-2) Im at the point where ∈aX^n-7∈a(n-1)X^n+10∈a(n-2)x^n=0 (terms of n are subscript) After this step it is given as replace the infinite sum by an expression ...
1
vote
1answer
895 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
1
vote
3answers
560 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
1
vote
2answers
69 views

solve the following recurrence exactly.

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)+t(n-4)&\text{otherwise.}\end{cases} $$ Express your answer as simply using the theta notation. I don't know where to go ...
1
vote
1answer
24 views

Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: rounding function)

I would appreciate if somebody could help me with the following problem Q: Let $(2+\sqrt{3})^n=a_n+b_n\sqrt{3}$ $(a_n,b_n,n\in\mathbb{N})$ . Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: ...
1
vote
1answer
63 views

Recurrence relation related proof

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .
1
vote
2answers
4k views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: $$P_n(x)=P_{n+1}'(x)-2xP'...
1
vote
1answer
181 views

Generating Function via Recurrence Relation

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated ...
1
vote
2answers
69 views

How to solve this mathematically

This is a question given in my computer science class. We are given a global variable $5$. Then we are to use keyboard event handlers to do the following: On event keydown double the variable and on ...
1
vote
2answers
401 views

Counting problem using exponential generating functions

From A Walk Through Combinatorics by Bona in the section on generating functions We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, ...
1
vote
2answers
109 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
1
vote
4answers
168 views

Find the solution to the following non-homogenous recurrence relation:

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} + a_{n+1} - 2a_n = n$ for $a_0 = 1$, $a_1 = -2$ I have found the homogenous part with the characteristic polynomial is $...
1
vote
2answers
2k views

Solving a recurrence relation using repeated substitution

So, basically I am having a big issue with this recurrence relationship: $$T(n) = T(n-1)+n, T(1) = 0$$ using repeated substitution I get down to: $$i=1, T(n-1) + n$$ $$i=2, T(n-2) + 2n - 2$$ $$i=...
1
vote
3answers
811 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: <...
1
vote
2answers
64 views

How does my professor come up with the recursive case in this algorithm analysis?

My professor gave us the following explanation for the recursive algorithm for finding the permutations of a set of numbers: When he has (T(m+1), n-1)) where does that come from? Why is it m+1 ...
1
vote
2answers
238 views

Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

I've been trying to find tight bounds for the equation: $$ T(n) = 2T(n/2) + n/\lg{n} $$ The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that ...
1
vote
1answer
88 views

Step by Step Second Order recurrence relations

Hi I have the following linear relation $S(n)= 2S (n-1)+3S(n-2)$ $S(1) = 3$ $S(2) = 1$ $S(3) = ?$ 1- I know I need to find $c_1$ & $c_2$ Which are $c_1 = 2 $, $c_2 = 3$ 2-I Know the ...
1
vote
2answers
149 views

Express sequence in closed type

Given the sequence $a_n = \sqrt{2+a_{n-1}}$. Is there anyway to find a closed form for this sequence? Thank you for your time.
1
vote
1answer
3k views

Difference equations and Matlab (some working)

The difference equations below model the yearly populations of wolves and moose, measured in hundreds. The wolves kill the moose for food. $$\begin{align} x_n&=x_{n-1}-0.004x_{n-1}+0.002x_{n-1}y_{...
1
vote
1answer
105 views

Recurrence $a_{n+1} = xa_n$ using generating function

I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ ...
1
vote
2answers
141 views

Recurrence relation: $x_{n+1} = \frac 12 x_n + \frac 1 {x_n},$ [duplicate]

$$x_{n+1} = \frac 12 x_n + \frac 1 {x_n}, x_0 \neq 0$$ $$ a = \frac a2 + \frac 1a \Rightarrow a = \frac {a^2 + 2} {2a} \Rightarrow 2a^2 = a^2 + 2 \Rightarrow a^2 = 2 \Rightarrow a = \pm \sqrt 2$$ If ...
1
vote
5answers
89 views

solution of recurrence relation $x_{n+1} = \frac {1}{x_n + 1}$

$$x_{n+1} = \frac {1}{x_n + 1}; x_1 > 0$$ How to transform it into the form $x_n = $? I need the solution in order to check if it converges at any $x_1 > 0$.
1
vote
2answers
597 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with $...
1
vote
1answer
476 views

Using partial fractions to find explicit formulae for coefficients?

The set of binary string whose integer representations are multiples of 3 have the generating function $$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$ Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings ...
1
vote
2answers
126 views

Solve non-homogeneous linear recurrence

I have the following recurrence $$a_n - 3a_{n-2} + 2a_{n-3} = 9 (-2)^n$$ with initial conditions $a_0 = 0, a_1 = 1, a_2 = 26$. I wish to find an explicit formula for $a_n$. The characteristic ...
1
vote
1answer
242 views

Help with a different approach to extracting a polynomial equation from differences

It is well known that we can determine the degree of a polynomial can be found by finding when the differences are the same. i.e. if the second differences are the same, it is a polynomial of the 2nd ...
1
vote
2answers
96 views

Help me solve this recurrence relation

I'm trying to solve the recurrence relation $$a_n = (\lambda +\mu)a_{n+2}+\mu a_{n+3}.$$ with initial relationships of: $\lambda a_1 = \mu a_2$ $(\lambda +\mu)a_2 = \mu a_3.$ I found a site ...
1
vote
1answer
51 views

a recurrence equation interpolating linear and exponential

$f(n+1) = f(n) + f(n)^{a}$ where $a \in (0,1)$ and $n \ge 1$ with $f(1) = m$. If $a=0$, we see $f(n) = m + n - 1$ and if $a=1$, we see $f(n) = 2^{n-1}m$. So the recursion seems to interpolate ...
1
vote
2answers
39 views

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ if $s_1 = 0, s_2 = 0, s_3 = 1$ I have attempted to use $p_n = c2^{n-2} - d$ [where $h_n = A(3)^n$, but to no avail] - i ended up with $c=-...
1
vote
1answer
42 views

Details about a Recurrence Relation problem.

I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step: If $H_n$ is the number of moves it takes for n rings to be ...
1
vote
1answer
166 views

How many times can a student skip class in a 14 weeks semester?

In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
1
vote
2answers
144 views

Recurrence equation

Given the following recurrence equation: $T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$ How would you set this equation up in order to allow you to solve it using telescoping? Thanks in advance.
1
vote
1answer
94 views

Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$

$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$ I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...
1
vote
2answers
63 views

How to think about solving recurrences?

I am having trouble finding a closed-form solution to the following recurrence for $T(i)$, $0\le i\le n$. $$T(0) = T(1) + 2,\quad T(n) = 0$$ and $$T(i) = {T(i+1)\over 2} + {T(i-1)\over 2} + 1,\quad ...
1
vote
1answer
105 views

How to find a closed formula for partial sums of recursively defined series with $t_{n} = t_{n-2} + t_{n-3}$?

If $1,1,2,2,3,4,5,7,9,12,16,21,28,37,\ldots,n$ - terms, $t_{n} = t_{n-2} + t_{n-3}$. Find the sum of such a series up to $n$ terms Progress Attempted to solve the recurrence relation $t_{n} = t_{...
1
vote
1answer
4k views

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
1
vote
3answers
230 views

Linear Recurrence Relations

I'm having trouble understanding the process of solving simple linear recurrence relation problems. The problem in the book is this: $$ 0=a_{n+1}-1.5a_n,\ n \ge 0 $$ What is the general process, and ...
1
vote
1answer
95 views

recursion relation for sequence of random variables

Let $\dots, \xi(-1),\xi(0),\xi(1),\dots$ be a sequence of i.i.d. random variables on $\mathbb Z$ with $\mathbb E[\xi(n)]=0, \mathbb E[\xi(n)^2]=1$. The process $(X(n))_{n\in \mathbb Z}$ is ...
1
vote
1answer
84 views

Recurrence Equation with Polynomial Coefficients

As inspired by this question on the problem site Brilliant, Let $F_n(a,b,c)=a(b-c)^n+b(c-a)^n+c(a-b)^n$ Is it possible to obtain $F_n$ in terms of $F_3, F_2$? My attempt at a solution is as ...
1
vote
1answer
65 views

Recursive sequence.

Given $a_0=0$, $\displaystyle a_n=\frac{3a_{n-1}+1+\sqrt{12a_{n-1}+1}}{3}$, find $a_n$ in terms of $n$. By finding the first few terms of $a$, I get a pattern and deduce that $a_n=n(n+1)/3$. I ...
1
vote
1answer
475 views

Program, Recurrence relation, Master-Theorem

Programming code: t(n) { for i=1 to n sum=sum+1 if (n>1) sum=sum+t(n/2)+t(n/2) return sum } I built the ...
1
vote
2answers
143 views

Solving a recurrence relation

I have a recurrence relation that I would like to solve. $T(n)$ belongs to $\Theta(f(n))$. $T(n) = 2T(\frac{n}{4}) + c$, where $c$ is a constant. The base case, $T(1)$ is a constant as well. My ...
1
vote
3answers
172 views

How to solve two recurrences dependent on each other

Let $F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$ $G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$ We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
1
vote
2answers
36 views

Solving a recurrence based on the solution to another.

I have a solution to a recurrence $g(n)=f(n) + g(n-1)$, and I'd like to solve the recurrence $h(n) = \alpha[f(n) + h(n-1)]$. I guessed the solution was $h(n) = \alpha^ng(n)$, but it turns out this ...
1
vote
1answer
77 views

Explicit formula for recurrence relation with $A_{N+1}= A_N+{(2/7)}^N$

How can I find a non-recursive formula for the sequence $A_N$ when the sequence is defined as $A_1=1$ and for $N\ge 1$, $A_{N+1}= A_N+{(2/7)}^N$?
1
vote
2answers
99 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
1
vote
1answer
90 views

Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
1
vote
2answers
681 views

How to find the order of a recurrence relation

I have some homework that I'm working on where there is a whole section of problems I need to solve taking the following form: "Assume that T(1) = 1, and find the order of function T(n)." I have no ...