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

learn more… | top users | synonyms (2)

3
votes
1answer
645 views

Boxcar Recursive Method for Finding Standard Deviation

I'm trying to develop a real time algorithm for finding level areas of an electrical signal. To do so I need to find the variance for a particular rolling time interval. From John Cook's blog and ...
3
votes
1answer
30 views

How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)
3
votes
1answer
48 views

Fibonacci-Like Sequence: Breeding Rabbits

I came across the following question on a math test: Suppose Fibonacci's research in the breeding habits of rabbits has been adjusted. They are now believed to be fertile after $2$ months of life, ...
3
votes
3answers
63 views

Set up difference equation for the following recurrence.

I have the following recurrence: $t=0: 0$ $t=1: 0$ $t=2: 1$ $t=3: \beta+\alpha$ $t=4: (\beta+\alpha)\alpha+\beta^2$ $t=5: ((\beta+\alpha)\alpha+\beta^2)\alpha+\beta^3$ ... I was hoping to do ...
3
votes
1answer
64 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
3
votes
1answer
131 views

How do I prove that the recurrence contains no perfect square?

Given the recurrence $$a_{n+2} = 14a_{n+1} - a_n - 6$$ with $a_1=1$ and $a_2=8$, how do I prove that none of the $a_n$'s apart from $a_1$ is a perfect square. This is not a homework problem, rather ...
3
votes
1answer
87 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
3
votes
2answers
41 views

Solve the recurrence relation by taking the logarithm of both sides and making the substitution $b_n = \lg a_n$

Solve this recurrence relation: $$a_n = \left(\frac{a_{n-2}}{a_{n-1}}\right)^{\frac{1}{2}}$$ by taking the logarithm of both sides and making the substitution $$b_n = \lg a_n$$ A couple years ago ...
3
votes
1answer
95 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
3
votes
4answers
156 views

General solution of recurrence relation if two equal roots

Consider the recurrence relation $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ If the characteristic equation $$ a\lambda^2+b\lambda+c=0 $$ has two equal roots, then the general solution is given by $$ ...
3
votes
1answer
53 views

Newton Rhapson Algorithm Accuracy

I read somewhere that the NR algorithm in general (given an appropriate initial value) increases in accuracy by roughly two decimal places per iteration. Is this something that can be proven, or is ...
3
votes
2answers
85 views

recurrent events-Probability of even number of successes

Let E be the event of an even number of successes. $u_n$:Probability of E occurring at the nth trial not necessarily for the first time $f_n$:Probability of E occurring at the nth trial for the first ...
3
votes
2answers
454 views

Recurrence Master Theorem Question with asymptotic Upper and Lower Bounds

If I were to solve the recurrence of following equation and give asymptotic upper and lower bounds: $$T(n) = 4T(\frac{n}{2}) + n^2 + n$$ Can I apply Master Theorem on this? My attempt was following: ...
3
votes
1answer
92 views

Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty $. ...
3
votes
1answer
102 views

Solving a recurrence relation ${}$

I feel I'm wasting my time trying to solve this $a_0$ is given $\displaystyle a_{n+1}=\frac{n-1}{n+2}(a_n-n-2)$ Mathematica found a closed form but there's a problem when evaluating for ...
3
votes
2answers
106 views

Fibonacci General Formula - Is it obvious that the general term is an integer? [duplicate]

Given the recurrence relation for the Fibonacci numbers, $F_{n+1}=F_{n}+F_{n-1}$ with $F_0=1$ and $F_1=1$ it's obvious that $F_n$ is a positive integer for all $n$. Suppose instead we were given ...
3
votes
5answers
159 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
3
votes
1answer
78 views

Expected Time for n Independent Prisoners to Escape

Suppose there are $n$ prisoners, and each day every prisoner independently has a probability $p$ of escaping. What is the expected length of time before all prisoners have escaped? Someone asked ...
3
votes
1answer
184 views

How to formalize in terms of category theory?

We define a recursive map as maps, $\chi \to \xi^{'}, \, \chi^{'} \to \xi^{''}, \, \chi^{''} \to \xi^{'''}, \ldots, \chi^{n} \to \xi^{n+1} \wedge \xi \to \chi, \, \xi^{'} \to \chi{'}, \xi^{''} \to ...
3
votes
1answer
192 views

Looking for the recurrence relation for certain trigonometric integrals

By assuming that: $$ \int_{\pi/4}^{\pi/2} \frac{\cos^4(x)}{\sin^5(x)}\,dx = k,$$ what does the integral $$ \int_{\pi/4}^{\pi/2} \frac{\cos^6(x)}{\sin^7(x)}\,dx$$ equal in terms of k? I have ...
3
votes
2answers
462 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 ...
3
votes
5answers
137 views

Simple functional equation

I have a simple functional equation: $$ \alpha(x) = {1 \over 2}\left[\alpha\left(x - 1\right) + \alpha\left(x + 1\right)\right]\,, \qquad \alpha\left(0\right) = 1\,,\quad\alpha\left(m\right) = 0 $$ I ...
3
votes
1answer
60 views

Find the number of ways that 2n people may be paired.

Question: Find the number of ways that 2n people may be paired. I have figured this problem out, and I'm fairly certain that there are $\frac{(2n)!}{2^{n} n!}$ ways. However, I cannot seem to work ...
3
votes
1answer
2k views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
3
votes
1answer
210 views

Generating and solving recurrence relations

I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated ...
3
votes
1answer
29 views

Probability, that when we send a $0$ down the network we will get back a $0$

We can send a $0$ or a $1$ over a network of $1,2...$ nodes. Unfortunately on each node with probability $p$ the message is not made different, and with probability $1-p$ the message is XOR'ed. Find ...
3
votes
2answers
164 views

Google Question: Number of ways to select sets such that n is pure

Consider a subset $S$ of positive integers. A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
3
votes
3answers
381 views

Help me to solve this recurrence relation for a closed form

I've tried my best to solve this recurrence relation into a closed form formula for generality but I couldn't. So, is there someone to help me to solve this recurrence relation into a closed form ...
3
votes
1answer
195 views

General solution to Wright-Fisher model - Diploid selection

Wright-Fisher models are classical theoretical results in evolutionary biology. There are two discrete time models, one for haploid selection and one for diploid selection (the meaning of these models ...
3
votes
1answer
256 views

Solving the recurrence $t(n)=t(n/2)+n^2$ using the iteration method

Any hints on how to solve $t(n) = t\left(\frac n2\right) + n^2$ with the iteration method? What I've got so far: $$t(n)=n^2+t\left(\frac n2\right)$$ $$t(n)=n^2+\left(\frac n2\right)^2+t\left(\frac ...
3
votes
4answers
2k views

Recursively defining the set of bit strings set having more zeros than ones

Question: Recursively define the set of bit strings that have more zeros than ones. I tried it this way: $\Sigma\subset \{0,1\}^*$ Basis step: $0 \in \Sigma$ Recursive step: For any $x\in ...
3
votes
3answers
144 views

General solution to a Growth equation

I'd like to compute a formula that describes a population growth. The population starts with $N(t=0)$ individuals. At each time step there are births and deaths. The number of births at time $t$ is ...
3
votes
2answers
1k views

Solving for the closed term solution of a third order recurrence relation with real constant coefficients

How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
3
votes
1answer
82 views

Asymptotics of a Recursively defined sequence

Suppose we define the sequence $a_n$ recursively by $p_1=1/2, a_1=2$, $p_{n+1}=p_n-\frac{{p_n}^2}{a_np_n+1}, a_{n+1}=a_n+\frac{1}{p_n}$. How does $(a_n)$ behave for large $n$? For instance, what is a ...
3
votes
1answer
691 views

why must orthogonal polynomials each have distinct roots?

Let $\langle\cdot,\cdot\rangle$ be any inner product on the set of functions $[a,b]\rightarrow\mathbb{R}$, and let $(p_n)_{n\in\mathbb{N}}$ be a sequence of polynomials defined by: $p_{-1}(x)=0$, ...
3
votes
1answer
480 views

Finding a Linear Recurrence Relation

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. ...
3
votes
3answers
222 views

“Fat” sets of integers and Fibonacci numbers

Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not. Define $f(n)$ to count the ...
3
votes
1answer
80 views

Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

I want to solve the following recurrence: \begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation} What are some basic "methods" I can use to guess a ...
3
votes
1answer
45 views

Is there a general formula for recurrence relations like $ f(x+1) = \sum_{i=0}^k a_n{[f(x)]}^n $

Or in other words, polynomial relation of the function rather than the argument. I've worked out that in general $ f(x+1)={f(x)}^n $ implies $$f(x) = C^{n^x} $$ for some C, but I would like to know if ...
3
votes
1answer
45 views

Could you please check if this substitution is right so far?

The question: Use resubstitution to solve the following recurrence equation: $$T(n) = 2T(n-1) + n;\; n \ge2\text{ and }T(1) = 1.$$ So far I have this: $$\begin{align}T(n) &= 2T(n-1) + n\\ ...
3
votes
1answer
519 views

Explicit Formula Given a Recursion

Suppose we have a function $f$ such that for positive integers $n \ge1$ and $f(0)=0$ and $f(1)=1$ we have: i) $f(2n + 1) = 2f(n) + 2$ ii) $f(2n) = f(n) + f(n − 1) + 2$ What is the generating ...
3
votes
1answer
141 views

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

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. ...
3
votes
1answer
318 views

Is this a correct way to convert an convolution equation into differential/difference equation?

For functions $f,g,h$ that are defined over $\mathbb{R}$, suppose we have a convolution equation: $$ f = g * h. $$ I would like to convert it into a differential equation. Is it correct that $$ ...
3
votes
2answers
60 views

Question about a recurrence

In a syllabus of mine, they try to find a closed form of the following recurrence relation $$\begin{align*} T(2k) &\leq 3T(k) + ck & k \geq 1\\ T(1) &= 1 \end{align*}$$ The method ...
3
votes
1answer
146 views

Perrin numbers in terms of the generalized hypergeometric function?

Given the roots of $x^3=x^2+1$, we have sequence A001609, $M(n) = x_1^n+x_2^n+x_3^n = \,_3F_2\left(\frac{-n}{3}, \frac{1-n}{3}, \frac{2-n}{3};\; \frac{1-n}{2}, \frac{2-n}{2};\; ...
3
votes
1answer
144 views

Sums of Fibonacci numbers

Given a multiset S of integers, when is $$\sum_{s\in S}F_{n+s}=kF_{n+t}$$ for some integers k and t and all integers n? $F_n$ is the n-th Fibonacci number. Essentially, given a sum of Fibonacci ...
3
votes
1answer
1k views

Dyadic Expansion-Proof?

Working through a measure theory textbook, and would like to understand dyadic expansions before I can understand its connections with the law of large numbers. I want to see this proved in detail, ...
3
votes
1answer
240 views

Identifying recursive polynomials

I need to evaluate the following function and want to proceed analytically as far as possible: $F(y) =e^{ i \beta \left ( y \frac{d}{d y} \right )^2} y \, e^{-y^2/2}$ My plan is to expand into ...
3
votes
4answers
2k views

Recurrence - Master Theorem - Asymptotic Question

Sorry if this question has been asked before, but I am trying to figure this out. I am using the CLRS text, Introduction to Algorithms. In the Recurrences chapter, in the Master Theorem section, the ...
3
votes
1answer
66 views

Is there a name for the this kind of recursive formula?

$a_{-i}=0$ for all positive i. We have the recurrence $$ a_n = \sum_{i=1}^\infty b_ia_{n-m_i} $$ Where $m_i>0$ for all $i$.