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

learn more… | top users | synonyms

1
vote
1answer
57 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
185 views

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

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
88 views

How to go about solving this recurrence relation?

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I ...
0
votes
0answers
26 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
0
votes
0answers
46 views

Removing the Summation (Closed Form)

The following question from "Combinatorics of Permutations" : $$ E[X] = \sum\limits_{k = 2}^n \frac{k\cdot T(n,k)}{n!} $$ where $$ T(n,k) = k \cdot T(n-1, k) + 2 \cdot T(n-1, k-1) + (n-k) \cdot ...
0
votes
1answer
29 views

Solving thus summation

$F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} (i > 2)$. A new number sequence $Ai(k)$ by the formula: $A_i(k) = F_i × i^k (i ≥ 1)$.I need to calculate the following sum: $A_1(k) + A_2(k) + ...
1
vote
3answers
54 views

solve the non homogeneous recurrence relation

These recurrences should be simple to solve but I see a ton of different ways to do it, such as general solution, particular solution etc. We did not talk about these in class, just need to get the ...
0
votes
0answers
13 views

General expression for this reccurent derivative?

I stumbled upon a problem that can be distilled to: Let $\Delta_m(x)$ be some function that depends on $x$ such that $$ \delta_{x}\Delta_m(x) = \Delta_{m+1}(x)$$ where $\delta_{x} $ is the ...
1
vote
3answers
160 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) } } ...
0
votes
0answers
18 views

How to solve this recurrence relation consisting of 9 equations (one of them with a minimum function)?

Given the recurrence relation as follows. $T_{k}=min((W_{k}+Y_{k}) , (X_{k}+Z_{k}))$ $A_{k}=T_{k}\frac{W_{k}}{W_{k}+Y_{k}}\frac{X_{k}}{X_{k}+Z_{k}}$ ...
0
votes
3answers
33 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
60 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
194 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
33 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
76 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
270 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
159 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
95 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
62 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
72 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
91 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
78 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
45 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
55 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
73 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
139 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
58 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
56 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
98 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
77 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
53 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
61 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
50 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
298 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
32 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
74 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
94 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
39 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
21 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
33 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
104 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
184 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 ...