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

learn more… | top users | synonyms

4
votes
1answer
935 views

Solving a recurrence relation with the characteristic equation

I have some trouble solving this due to not seeing the steps to be able to feed it into the characteristic equation. $$T(n) = 4T(n-2) +n + 2^nn^2\ \text{with}\ \ T(0)=0,\ T(1)=1$$ (don't have to ...
1
vote
1answer
191 views

solution to non-linear difference equation

Did anyone ever come across the global solution for a non-linear difference equation that looks like this: $y(t+1)=y(t)+a+b \sqrt{c y(t)+d}$. The initial condition is $y(0)=y_0$, and a,b,c and d are ...
0
votes
2answers
156 views

Resolve this recurrence: $T(2^n) = T(2^{n-1}) + 2^n$

I need to resolve this recurrence: $$T(2^n) = T(2^{n-1}) + 2^n$$ The conditions are: Give a $\theta$ bound. In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ...
7
votes
6answers
386 views

Finding the $n$-th deriviative of $f(x) =e^x \sin x$, solving the recurrence relation

I was given a homework assignment to find a closed solution for the nth deriviative of the function: $f(x) = e^x \sin x$ So far I have been able to obtain the derivative as: $f^{(n)}(x) = e^x S_n ...
0
votes
1answer
166 views

Convert a recurrence relationship into an algebraic equation

I have a piece of code that describes a recursive relationship to produce a logarithmic sweep: ...
0
votes
0answers
141 views

Given a state transformation matrix and a state vector, how to find the total number of changes for each individual element.

I have a vector of binary variables, $s$ representing a state at some point in time, and a transformation matrix $T$. The initial state is $s_0$. $s_n = Ts_{n-1}$ Given a number of transformations, ...
1
vote
6answers
438 views

Solving Recurrences using Telescoping/Backwards Substitution

Specifically, $$T(n)=3T(n-1)+1; \quad T(1)=1.$$ I have \begin{align*} T(n) & = 3T(n-1)+1 \\ & = 3(3T(n-2)+1)+1 \\ & = 9T(n-2)+4 \\ & = 9(3T(n-3)+1)+4 \\ & = 27T(n-3)+13 \\ & ...
0
votes
1answer
104 views

Showing a recurrence is $\Theta$(n)

Specifically how do you go about showing that $$ 2T(n/2)+1 =\Theta(n) $$ Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in ...
11
votes
3answers
2k views

Solving recurrence relation in 2 variables

We already know how to solve a homogeneous recurrence relation in one variable using characteristic equation. Does a similar technique exists for solving a homogeneous recurrence relation in 2 ...
0
votes
0answers
42 views

Circular permutation of $k$ types of items on $n$ places with no two adjacent items of the same type. [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? I have been trying to work out a problem but cannot get any closed formula or recurrence. You are ...
4
votes
3answers
129 views

How do you solve this recurrence?

I have been trying to practice recurrence relations that can be solved by the master theorem and came across this. Now the $4^{\textrm{th}}$ problem in that file is : $$T(n) = 2^n ...
0
votes
1answer
226 views

How do you get the upper bound over this recurrence?

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$ I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. ...
2
votes
1answer
124 views

Difficult partial solution to a reccurence equation

I am trying to help a friend of mine solve $$ a_n + 5 a_{n-1} + 6 a_{n-2} = 12n - 2(-1)^n$$ Now the homogenous solution is easy to find, and one just needs to solve the equation $r^2 + 5r + 6 = 0$ ...
14
votes
6answers
1k views

How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

How to solve this particular recurrence relation ? $$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$ such that $f_2 = 12, f_3 = 24$ and so on. I tried out a lot but due to $(-1)^n$ I am not able to ...
1
vote
1answer
103 views

Solve recurrence: $T_n =\frac{1}{n}(T_{n-1} + T_{n - 2} + T_{n - 3} + \dots + T_2 + T_1 + T_0) + 1$ with $T_0 = 0$

Solve recurrence: $T_n =\frac{1}{n}(T_{n-1} + T_{n - 2} + T_{n - 3} + \dots + T_2 + T_1 + T_0) + 1$ with $T_0 = 0$. The recurrence is defined only on nonnegative integers. Thanks.
4
votes
4answers
161 views

What sort of math is this, and how would I solve it?

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
1
vote
1answer
726 views

Recursion relation for the number of ternary string that does not contain two consecutive characters.

Ternary strings are those that contain only 3 characters at most. For ex: abcbca is ternary string over set {a,b,c}, etc. Can anyone tell what will be the recursion relation for the string that does ...
1
vote
0answers
151 views

two dimensional recurrence

We have the following recurrence relation for $a_{n,m}$ $a_{n,m}=4a_{n+1,m-1}+\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$ with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ ...
1
vote
0answers
155 views

Evaluating iterated sine function

Let $f(x,1)=\sin(x)$ and $f(x,i)=f(\sin(x),i-1)$ ($f$ is the iterated sine function). For arbitrary $N$,$x_0$, how quickly can $f(x_0,N)$ be computed? Answer to this question discusses ...
4
votes
1answer
178 views

Recurrence relation for a function with an integral of the function?

Pardon my lack of tex skills, but what is the recommended procedure in the following scenario: $$g(f) = 1+\int_0^{1-f} g\left(\dfrac{f}{1-x}\right)\,dx$$ I am not sure how to proceed in such a ...
1
vote
1answer
58 views

How to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?

Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one? For example, I might want to approximate $$ ...
0
votes
2answers
147 views

Evaluating a recurrence relation with non-contiguous initial conditions

Is there a general way of evaluating the points in a recurrence relation when the initial conditions are not contiguous? For instance: $$T(i) = f\left(T(i-1), T(i-2)\right),$$ with $T(a) = A$ and ...
0
votes
2answers
61 views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n) = \Theta(n^2) $ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2 $. I don't understand how to subtract off ...
1
vote
1answer
51 views

Estimation of recurrent sequence

Suppose we have $z_{n+1}=\frac{z_{n}^2}{1+cz_{n}}$ where $c>1$ and $z_{1}>0$. What can we say about $z_{n}$? Can we find an explicit formula? Can we at least get an approximation of the form ...
1
vote
2answers
736 views

Proving convergence of a recurcive sequence $a_{n+1}=\ln(a_{n}+2)$.

Suppose we have a sequence defined by $a_{n+1}=\ln(a_{n}+2)$. We want to prove that for every $a_{0}>0$, the sequence converges to the same $g\in\mathbb{R}$. This is where I got so far: Let's ...
1
vote
1answer
113 views

Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
2
votes
2answers
378 views

How to solve this recurrence relation $T(n) = T(n/5) + T(4n/5) + O(1)$

Given the recurrence: $$T(n) = T(n/5) + T(4n/5) + O(1)$$ The annoying part is $O(1)$. If it were some $g(n)$, then I could use recursion tree on $n$, but there is no such $n$ to start with. So I ...
5
votes
4answers
4k views

What is the solution to the following recurrence relation with square root?

This looks like a question asked earlier, but it isn't T(n) = T (sqrt(n)) + 1 ... if n>1 =1... if n=1 My professor gave this to me in class yesterday. This is where I'm stuck.. T(n) ...
0
votes
1answer
82 views

Recurrence equation and special functions

Can someone give me a proof or a hint on why the recurrence equation: $$g(k+2)=k*g(k+1)-g(k)$$ has the solution: $$g(k)=c_1 {_0\tilde F_1}(;k;-1)+c_2 Y_{k-1}(2)$$ where ${_0\tilde F_1}(;a;x)$ is the ...
3
votes
1answer
128 views

Asymptotic of $T(n) = T(n-2) + \frac{1}{ \lg n}$

Trying to determine asymptotic of $$T(n) = T(n-2) + \displaystyle\frac{1}{ \lg n}$$ $$\lg n = \log_{2}n $$ Last term $\frac{1}{ \lg n}$ give me a lot of trouble. Iterative method doesn't work. ...
2
votes
2answers
86 views

Asymptotics of $nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$. Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came ...
2
votes
1answer
135 views

How can I express such function as known functions or power series?

$$\int_0^x \cfrac{1}{1+\int_0^t \cfrac{1}{2+\int_0^{t_1} \cfrac{1}{3+\int_0^{t_2} \cfrac{1}{\cdots} dt_3} dt_2} dt_1} dt =f(x)$$ $$\int_{0}^{x} \frac{1}{n+h_{n+1}(t)}{d} t=h_n(x)$$ ...
19
votes
4answers
454 views

recurrence relation arising from Magic the Gathering scenario [duplicate]

Possible Duplicate: Probability of a random binary string containing a long run of 1s? EDIT: Cocopuffs below has partially answered the question, but the critical base case $L=2$ to his ...
1
vote
0answers
188 views

Closed form expression for a recurrence relation.

Hello, any ideas for computing closed form for a recurrence relation? In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
1
vote
2answers
3k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
3
votes
1answer
526 views

Binary Strings of the form *111* [duplicate]

Possible Duplicate: Counting subsets containing three consecutive elements (previously Summation over large values of nCr) Given an integer $N$, we have to count the number of possible ...
3
votes
3answers
137 views

In how many sequences of length $n$, the difference between every 2 adjacent elements is $1$ or $-1$?

How do I find a recursion formula to solve the following question: In how many sequences of length $n$, with elements from $\{{0,1,2,3,4}\}$, the difference between every 2 adjacent elements is $1$ ...
3
votes
1answer
370 views

Solution to a second order recurrence relation with non constant coefficient

I have the following equation: $(aq^n+b+s)C_n(s)=aq^nC_{n+1}(s)+bC_{n-1}(s)$ , for $n\geq1$. $C_0(s)=1$ , and for all $s\geq 0$ we have $0\leq C_n(s)\leq1$. $a>0$, $b>0$, $0\leq q\leq1$. ...
4
votes
1answer
301 views

Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:-- $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$ I tried using Binet's equation but I am ...
7
votes
1answer
221 views

Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $

I have a recurrence relation, $$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$ I have to find the value of $a_n$ for very large values of n. I tried ...
1
vote
2answers
394 views

solving inhomogeneous recurrence relation

I had encountered an inhomgeneous equation of the type : $$f(n)=h(f(n))+g(n)$$ below is the equation. $$f(n)=\begin{cases} f(n-1)+2^{(n-1)/2},&\text{if }n\text{ is odd}\\\\ ...
9
votes
1answer
310 views

Recurrence equation similar to a geometric progression

I have the following recurrence relation: $$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$ with $k \geq 0$, a fixed constant. I know that when $k=0$, we have: $$T(i) = \sqrt{T(i-1) T(i+1)},$$ which ...
2
votes
3answers
135 views

Corresponding numerator of the fraction

I am stuck at this question cant think of how to resolve this, sorry I did try to do working but can't think of any right solution. The question is If the denominator is $9900$, then what is the ...
3
votes
1answer
908 views

In how many different ways can we fully parenthesize the matrix product?

We have a finite number of matrices that we wish to compute the product of . Say we wish to compute a product of n matrices and we have the subroutine to compute a ...
0
votes
0answers
41 views

Estimating the recurrence $T(n,i) = (\lfloor\frac{n-i}{i}\rfloor \cdot i ) + T(i + (n \operatorname{rem} i), (n \operatorname{rem} i))$

Given $i < n/2$ and denoting $[x]$ to be an integer part of $x$ (floor$(x)$) and $(a \operatorname{rem} b)$ to be a reminder when $a$ is divided by $b$. $$ T(n,i) = ...
2
votes
6answers
275 views

I know that, $S_{2n}+4S_{n}=n(2n+1)^2$. Is there a way to find $S_{2n}$ or $S_{n}$ by some mathematical process with just this one expression?

$S_{2n}+4S_{n}=n(2n+1)^2$, where $S_{2n}$ is the Sum of the squares of the first $2n$ natural numbers, $S_{n}$ is the Sum of the squares of the first $n$ natural numbers. when, $n=2$ ...
1
vote
1answer
81 views

Complexity of recurrence equation

what is the complexity of this equation ? $T(n) = 2*T(\sqrt n) + \log n$ and T(2) = 1.
2
votes
1answer
427 views

How to complete this proof regarding closed form of tower of hanoi problem? [duplicate]

Possible Duplicate: can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer I'm trying to learn induction through practise and I'm ...
2
votes
1answer
64 views

Flawed twofold induction on an inequation (but where?)

The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...