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

learn more… | top users | synonyms (2)

0
votes
1answer
44 views

Finding the recurrence relation? [duplicate]

If I let $n \geq 1$ be an integer and use a $2 \times n$ board $D_n$ containing $2n$ cells, each side has a length of 1. T The brick can be vetical or horizontal containg $2$ cells(explained in the ...
0
votes
3answers
2k views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
4
votes
3answers
174 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
1
vote
1answer
121 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
-1
votes
1answer
231 views

Recurrence relation with complex roots

$$a_n=4a_{n-1}+5a_{n-2},\quad a_1=2,a_2=6$$ $$x^2-4x-5=0$$ $$x=-2+i,-2-i$$(complex roots) as per the quadratic equation for the roots, $$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$ Then what is the formula ? ...
1
vote
2answers
124 views

Is there a method for finding the fixed point of logarithmic functions?

I am faced with this function (warning, I am not good at math) $x(t+1)=0.5 \ln x(t)+1$ initial condition = 1 . I know the fixed point is 1 because $0.5 \ln (1)+1=1$ but I wanted to know the ...
0
votes
1answer
112 views

Deriving recurrences?

Hi could some do this question for me I have never derived a recurrence before For an integer $n \geq 1$, draw $n$ straight lines, such that no two of them are parallel and no three of them ...
0
votes
1answer
44 views

Solving a Recurrence Relation

In my research, I encountered the following recurrence relation: \begin{align} g(t) &= (\beta-1) \; g(t-1) + \beta \; f(t)\\ f(t) &=\min\{f(t-1)+g(t-1), \, c \cdot \lambda^t \} \end{align} ...
1
vote
1answer
117 views

What's a useful recurrence relation for $(2n)!$ in terms of $n!$?

I want to make an algorithm for $n!$ which will divide the number in half and call the algorithm again until n is so close to $0$ that a value of $1$ can be safely returned, and use the value of each ...
2
votes
2answers
107 views

Process of solving recurrence relations

I am having trouble understanding how to solve a recurrence relation. If you can please help walk me through this one: $T(n) = T(\dfrac{n}{2}) + 5$ Initial conditions $T(0) = 0$ and $T(1) = 1$ My ...
0
votes
2answers
50 views

Solve recurrence relation for given n

How do I approach the problem if I have given n. The question is to find $T(1024)$ when: $$T(n) = 2T(n/4) + 4n + 8\text{ for }n > 1 \\ T(1) = 1 $$ Do I just substitute? In that case I get: ...
0
votes
1answer
79 views

Recurrence relations

I am trying to solve the following recurrence relation: $$ T(n) =\begin{cases} 4T(n-1) & \text{, if }n\gt1\\1 & \text{, if }n=1 \end{cases} $$ This is what I have got so far: $$4T(n-1)+2$$ ...
0
votes
2answers
45 views

How to find the linear recurrence in this case?

Suppose $c_0$, $c_1$, $c_2$ satisfies the recurrence $c_n = 3c_{n−1} − 3c_{n−2} + c_{n−3}$ for $n ≥ 3$. Let $a_n = c_{n+1} - c_n$ for $n \geq 1$, and $a_0 = 0$, how to find a linear recurrence of ...
0
votes
1answer
78 views

How to solve this recurrence of a sequence?

$x_1=1$, $x_2=2$, $x_n=n\cdot x_{n-1}+\frac{n(n-1)}{2}x_{n-2}$ Thanks to Barry Cipra's suggestion, now I have obtained the solution for $x_n$: ...
2
votes
2answers
52 views

Determining Values

I have tried a couple of ways to get started / finish this problem but I cant seem to figure out how to fully explain and determine the value of $x_n$. I have posted my question below with figures to ...
3
votes
2answers
349 views

How to find fixed point

I have recurrence equations of \begin{align*} x_{n+1} &:= 0.5\cdot (x_{n}^2+2\cdot y_{n}-2\cdot x_{n}\cdot y_{n}-2\cdot y_{n}^2) \\ y_{n+1} &:= -0.8\cdot (x_{n}^2+2\cdot y_{n}-2\cdot ...
1
vote
2answers
73 views

How to find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / b(x)$?

Consider the sequence $c_0, c_1, c_2,\ldots$ satisfying $c_i =2\cdot 3^i − i^2\cdot(−1)^i$. Let $c(x) = c_0 + c_1x + c_2x^2 + \ldots$ Find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / ...
5
votes
0answers
75 views

Right way to solve this reccurence relation?

I am not that good in mathematics , I have solved many simple relations. But I am not be able to solve the following. This is not a homework. I found it during analysis of a program. ...
1
vote
2answers
60 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 ...
2
votes
3answers
125 views

How to tackle a recurrence that contains the sum of all previous elements?

Say I have the following recurrence: $$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$ where $n = ...
0
votes
1answer
65 views

Prove that the recurrence is true [duplicate]

I am working on an assignment question, and am having trouble moving ahead. The question is as follows: Let the total number of bit strings with three consecutive zeros be $t_n$. Prove for $n \ge ...
0
votes
2answers
98 views

Recurrence relation of order $n$: $f(n) = \dfrac{1}{k-1}\sum\limits_{i=1}^n {n \choose i} f(n-i)$.

I came across this recurrence relation while looking for a closed form for $S(n,k) = \sum\limits_{i=0}^\infty \dfrac{i^n}{k^i}$.After a few manipulations, I came across this recurrence relation: $f(n) ...
0
votes
1answer
132 views

Using induction to prove a general form from a recurrence relation

I have the recurrence relation: $a_{n+2} = \dfrac{-a_{n}}{(n+2)(n+1)}$. I have done some work to identify that two cases emerge: one is n is positive, and one if n is negative. If n = 2m (even) ...
1
vote
1answer
64 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
0
votes
1answer
54 views

Master Theorem Question

I need to solve the following: $T(n)=T(n-1)+8$ I've tried doing $a=1$, $b=-1$, and $d=8$ but $\log_{-1}1$ doesn't make sense. Any suggestions?
5
votes
1answer
413 views

Purely combinatorial proof and simplification of identity involving factorials and summations

While trying to decompose factorials into summations, I came up with the following identity $$(n+2)! = 2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}\sum\limits_{S \subseteq ...
0
votes
1answer
47 views

Recurrence relation for $n$ digit numbers not containing '$20$'

How many n digits base $3$ numbers do exist such that they never contain pattern '$20$'? (first find a recurrence relation)
3
votes
2answers
98 views

recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ ...
2
votes
0answers
107 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
0
votes
1answer
27 views

Characteristic equation of a difference equation indicates the function behavior

For the characteristic equation $a_2 \lambda^2 + a_1 \lambda + a_0 = 0$ of the difference equation $a_2 x_{n+2} + a_1 x_{n+1} + a_0 x_n = 0$, I remember there is a way to indicate if the function of ...
1
vote
4answers
42 views

Identity for this recursive relation with multiple terms

I have a recursive relation algorithm which is defined as follows: $$F_n = 3(F_{n-1} - F_{n-2}) + F_{n-3}$$ $$F_0 = 0$$ $$F_1 = 1$$ $$F_2 = 4$$ From calculating the first few values, I know this is ...
0
votes
1answer
38 views

How do we solve a tight big-O bound for the recurrence $T(n) = T(n^{2/3}) + 1$?

The big-O bound seems largely governed by how many times we can take the input $n$ by the $\frac{2}{3}$ power until it reaches some constant like 1. How do I start formalizing this problem in math ...
1
vote
2answers
52 views

How do we solve the exact recurrence for $T(1) = 1, T(n) = 3T(n - 1) + 2n + 2$ for $n > 1$?

This looks like an exponential recurrence due to the 3 behind $T$, but I'm not sure how to formally solve for $T(n)$ without $T$ on the righthand side.
2
votes
1answer
41 views

Four or More Heads in a Coin Toss

How would one write a recursion for the number of ways to get 4 or more heads in a row in 10 tosses of a coin? Would it suffice to use the recursion H(n)=H(n-1)+H(n-2)+H(n-3)+H(n-4) for the number of ...
3
votes
3answers
200 views

Why does this recurrence relation generate a sinusoidal curve?

I came across the following coupled recurrence relation while watching this video called Media for Thinking the Unthinkable: $a_{n+1} = a_n - 0.069\cdot b_n$ $b_{n+1} = b_n + 0.069\cdot a_{n+1}$ ...
12
votes
1answer
205 views

Family of GCDs all equal to $2$

Is it true that $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ for all $n \in \mathbf{Z}_{\geq 0}$? I'm continually stumped with this and verifying it numerically is quite expensive very ...
0
votes
1answer
314 views

Solving a recurrence involving floor and square root (Concrete Mathematics 3.28)

I'm working through Concrete Mathematics and having trouble understanding an answer to a problem (as well as what I could've done to come up with the answer). Problem 3.28 asks: Solve the recurrence ...
0
votes
2answers
120 views

Combinatorics - Check my answer, sitting order, round table.

$n$ people are sitting at a round table with $n$ seats at a restaurant. The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 ...
4
votes
1answer
210 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
3
votes
3answers
96 views

Recurrence $f(a,b)=f(a,b-1)+2f(a-1,b-1)$

Consider the recurrence relation $$f(a,b)=f(a,b-1)+2f(a-1,b-1)$$ for integers $a,b\geq 2$, where $f(a,b)=1$ if $a=1$ or $b=1$. Is it possible to find a closed form for $f(a,b)$?
0
votes
1answer
115 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
0
votes
1answer
67 views

Can every recurrence relation be solved?

Motivation A possible way to solve an ODE is to express the solution as: $y= \sum_{n=0}^\infty a_nx^n$. We substitute in the ODE and then calculate the coefficients $a_n$. For example, $y''+y=0$ ...
0
votes
1answer
59 views

Master's theorem applicability.

I have to find out if the following recurrence can be solved with the master theorem: $$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$ I have figured that, here, I have the third case because ...
4
votes
0answers
96 views

if $(n+1)c_{n}=nc_{n-1}+2nd_{n-1},d_{n}=2c_{n-1}+d_{n-1}$How prove $c_{n},d_{n}$ are integers

let sequences $c_{n},d_{n}$ such $$c_{0}=0,d_{0}=1$$ and for $n\ge 1$,have $$c_{n}=\dfrac{n}{n+1}c_{n-1}+\dfrac{2n}{n+1}d_{n-1}$$ $$d_{n}=2c_{n-1}+d_{n-1}$$ show that $c_{n},d_{n}$ are integers. my ...
0
votes
1answer
178 views

Plot of recurring system in MATLAB, Lozi map

I need to write this recurring system in MATLAB $$ x_{n+1}=1-a|x_n|+y_n$$ $$ y_{n+1}=bx_n $$ and take its plot for every $x_i,y_i$,with let's say a=1.4 and b=0.7. $$$$This is the Lozi map. And this ...
1
vote
0answers
46 views

Recurrence of a function

Consider the following recurrence: $$ T(n) = 2T(n/2)+n\lg n$$ Let’s use a base-case $T (2) = 2$ and let’s assume $n$ is a power of $2$. (a) “guess and prove by induction” method, considering the ...
2
votes
3answers
50 views

Help with recurrence relation

It 's been a long time since I touched this kind of math , so please help me to solve the relation step by steps : $V_k = (1+i)*V_{k-1}+P$ I know the answer is $V_k = (P/i)*((1+i)^k-1) $ Thanks ...
6
votes
0answers
169 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
3
votes
1answer
27 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
1
vote
0answers
44 views

Algorithms: Recurrence

Here's a problem that I am struggling with... If two algorithms A and B both solve the same problem. On an input of size $n$ Algorithm $A$ breaks it into $5$ pieces of size $n/2$, recursively solves ...