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

learn more… | top users | synonyms

0
votes
3answers
34 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
2
votes
2answers
75 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
5
votes
2answers
197 views

Dynamics of the repetitions of $f(z) = z^{2} +\frac{1}{4}$

This is probably a classic and most likely an easy question, but I was not able to find an answer. If we have the iteration $z_{n+1}=g(z_n)$, where $$g(z) = z + a z^{2},$$ with $a\ne 0$, then using a ...
1
vote
2answers
35 views

Find the linear reccurence of degree at most 2 of most 2 for the following sequence

Suppose $a_0,a_1,a_2$ satisfy the recurrence $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n\ge3$ Let $c_n=a_{n+1}-a_n$ for $n\ge1$ and $c_0=0$ Find a linear recurrence of degree at most 2 for the ...
0
votes
1answer
34 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 ...
2
votes
1answer
85 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
0
votes
3answers
425 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
160 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
101 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
65 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 ? ...
0
votes
1answer
74 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
35 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
96 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
84 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
46 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
59 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
44 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
74 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
49 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 ...
2
votes
2answers
159 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
70 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
61 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
57 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
101 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
61 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
79 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
64 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
62 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
52 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
336 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
33 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
78 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
95 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
25 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
40 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
28 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
49 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
34 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
110 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}$ ...
11
votes
1answer
186 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
172 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
97 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 ...
3
votes
1answer
145 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
94 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
73 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
60 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
46 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
90 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
131 views

Backwards Recurrence [duplicate]

For $$I_n = \int_0^1 \frac{x^n}{x + \alpha}\,{\rm d}x$$ $\alpha$ constant parameter We know $I_0$ = log[ $\frac{1 + \alpha}{\alpha}$] and we can derive a recurrence formula for $I_n$: $I_n = \frac 1n ...
0
votes
1answer
93 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 ...