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

learn more… | top users | synonyms

1
vote
0answers
73 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
0
votes
1answer
39 views

Simple qustion about Induction

I need to prove T(N) = O(N) $T(n) = T([3N/4] )+ T([N/4] ) + 1$ I think a good way to solve is to prove that T(N) < N-1 Induction hypotysis: for N-1, prove for N: $T(n) = T([3N/4])+ T([1N/4]) + ...
1
vote
1answer
179 views

How to solve non-homogeneous recurrence relation?

The relation is $$T(n) = T(n-1)+T(n-2)-T(n-3)+1 \quad \quad (1)$$ I tried in this way but stuck at a point . Please Help $$T(n+1) = T(n)+T(n-1)-T(n-2)+1 \quad \quad (2)$$ Subtracting $(2)$ from ...
1
vote
1answer
149 views

what to do next recurrence relation when solving exponential function?

find gernal solution of :$a_n = 5a_{n– 1} – 6a_{n –2} + 7^n$ Homogeneous solution: $a_n -5a_{n– 1} + 6a_{n –2} = 7^n$ put $a_n=b^n$ $b^n -5b^{n– 1} + 6b^{n –2} =0$ $b^{n-2} (b^2-5b^{} + 6b) =0$ ...
2
votes
3answers
291 views

Monotone and Bounded Sequences: Proof

Say $s_1=1$ and $s_{n+1}=\frac{1}{5}(s_n+7)$ for $n\geq 1$. Prove that the sequence is monotone and bounded, then find the limit.
1
vote
1answer
100 views

Recursive and closed form solution for choosing $n$ pairs/triplets.. of $kn$ elements.

I stumbled apon an interesting question: How many ways are there to arrenge $kn$ elements into $n$ sets, $k$ elements each? There should be a recursive and closed form solution for $g_k(n)$. For ...
2
votes
2answers
75 views

If $a_{n+1} = u a_n+v a_{n-1}$, what recurrence does $a_{n+1}a_n$ satisfy?

If $a_{n+1} = u a_n+v a_{n-1}$ , what recurrence does $a_{n+1}a_n$ satisfy? You can assume that $u^2+4v > 0$. A starter question, which I have done some work on: If $a_{n+1} = 3 a_n - a_{n-1}$ , ...
2
votes
1answer
87 views

Questions about $\ln(z)$ recurrence and fixed points.

Define property $A_R$ for an analytic function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ for $|z|<R$ where $R$ is a radius. And $f(z)$ is analytic within the radius $R$ ...
0
votes
1answer
60 views

Recurrence Equation

I have a problem with this type of non-homogeneous equation. Find the solution of recurrence equation: $2 A_{n+1} = 3A_{n}-n+2$ $A_{0} = 1$ I know the idea behind the problem when the particular ...
2
votes
1answer
41 views

Question about fixpoints and zero's on the complex plane.

Define property $A$ for an entire function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ $2)$ $f(z)=z$ has exactly one solution $=>z=0$ (follows from $1)$ ) $3)$ $f(z)$ is not a ...
1
vote
1answer
63 views

Inequality With Recurrent Relation

$a_{1}=1$, $~$ $a_{n+1}-a_{n}=\sqrt{\dfrac{a_{n+1}^{2}-1}{2}}+\sqrt{\dfrac{a_{n}^{2}-1}{2}}$ , $~$ $a_{n+1}>a_{n}$ Prove that $~$ $\displaystyle\sum_{k=1}^{\infty}\frac{1}{a_{n}}<e$
1
vote
1answer
107 views

Proving the recurrence relation $xL_n'(x) = n l_n(x) - n L_{n-1}(x)$

How can I prove the following recurrence relation for Laguerre polynomials eqn $(11)$. $$xL_n'(x) = n L_n(x) - n L_{n-1}(x)$$ I managed to show that the following which seems to be true. I put all ...
43
votes
3answers
812 views

How prove this nice limit $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

Nice problem: Let $a_{0}=1$ and $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Show that ...
2
votes
4answers
57 views

Closed form solution to simple recurrence

I have this recurrence : $$f(i) = \begin{cases} 0 &i=0\\ 1 &i=M\\ \frac{f(i-1) + f(i+1)} 2& 0 < i < M \end{cases}$$ I have guessed that $$f(i) = \frac i M$$ and proved it via ...
2
votes
2answers
178 views

Solving $ T(n) = 1 + 2( T(n-2) + T(n-3) +\cdots+T(0) ) $

I have the following recurrence relation which I have obtained from an algorithm: $$ T(n) = 1 + 2( T(n-2) + T(n-3)+\cdots+T(0) ) $$ with base case $T(0) = 1$ and $ T(1) = 1 $ I would like to be ...
33
votes
5answers
850 views

How much weight is on each person in a human pyramid?

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of ...
5
votes
2answers
109 views

Why should we suspect that the recurrence $T(n) = T(n-1) + n(n-1)$ satisfies a polynomial identity?

In the question Algorithms: Recurence Relation, the author asked about the recurrence relation $$T(n) = T(n-1) + n(n-1)$$ and one of the answers proposed assuming $T(n)$ is polynomial, then ...
1
vote
4answers
61 views

Algorithms: Recurence Relation

Can someone please help me solve this recurrence relation using back substitution method: $$T(n) = T(n-1) + n(n-1)$$ Base case is T(1)=1. Also, what is the asymptotic notation? Explanation of steps ...
2
votes
0answers
36 views

recurrence relation dependent inversly on n

Is there any efficient way to solve $F(n)=F(n-1)+1/n$ on $\mathcal{O}(\log n)$ time like we have matrix expo. for fibonacci series ?
5
votes
1answer
202 views

Deriving a recurrence relation

The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ ...
0
votes
0answers
90 views

Sum of two Bessel function of first kind

I want to find an expression for the sum of two Bessel functions of first kind with the same argument but a different order, i.e. $F(i,j)=|J_{i+j}(x)+(-1)^j J_{i-j}(x)|^2$. Is there any way of ...
0
votes
0answers
58 views

How to solve the recurrence relation $f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$ to find a closed-form solution?

A friend of mine gave me a math problem whose answer turned out to be $$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$ for some fixed $p$. I'm trying to find a closed-form solution to the ...
2
votes
2answers
78 views

A Recurrence Equation From a Game

$a_n=a_{n-1}(a_{n}-a_{n-2}+1)$ The above equation is defined in $[0,m]$ st. $a_{0}=0$ and $a_m=1$. It turned up as I was trying to analyze a simple richman game. I have managed to solve the equation ...
1
vote
2answers
89 views

How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$?

How to solve the following recurrence relation $$f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$$ with the initial conditions $f_{1}(x)=x, f_{2}(x)=x^2-1$? The answer is that ...
0
votes
1answer
102 views

Getting the closed form solution of a third order recurrence relation with constant coefficients

This is part of the proof of finding the closed from solution of third order recurrence relation I know that the closed form will look like the following And this is the part of the proof I can ...
1
vote
2answers
73 views

Can I get a hint on solving this recurrence relation?

I am having trouble solving for a closed form of the following recurrence relation. $$\begin{align*} a_n &= \frac{n}{4} -\frac{1}{2}\sum_{k=1}^{n-1}a_k\\ a_1 &= \frac{1}{4} \end{align*}$$ The ...
0
votes
2answers
414 views

Finding the closed form solution of a third order recurrence relation with constant coefficients [duplicate]

How would you solve for the closed form solution of a(n) given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
0
votes
2answers
114 views

Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...
0
votes
2answers
77 views

A basic problem on recurrence relation

How to solve this recurrence relation $a_n=(1-p) + (2p-1)a_{n-1}, n \geq 2$ where $a_1= \beta$ and $p$ some arbitrary number.
0
votes
0answers
51 views

recursive inequalities

I have a system of two recursive equations of which I am trying to explore some basic properties. I would like to look at specific conditions where some inequalities hold but it is tough since they ...
9
votes
3answers
273 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
-7
votes
1answer
51 views

Recursive definitions - cannot figure this one out

I need to find a recursive solution to the below problem. $$a_n=n(n-1)$$ for $n \in \mathbb{N}$ Calculating some values gives \begin{align*} a_1&= 1\cdot (0)=0\\ a_2&= 2\cdot (2-1)=2\\ ...
3
votes
1answer
2k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
0
votes
1answer
98 views

Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
0
votes
1answer
46 views

Recipe for solving linear discrete-time model for which N(t) is influenced by N(u) and N(v) u<t, v<t.

For solving linear discrete time model of the form $$N_{t+1}=pN_{t}+c$$ (when saying solving I mean that $N_{t}$ is expressed only in function of $p$, $c$ and the initial conditions) one can first ...
1
vote
2answers
60 views

Find the value of the the term

The sequence $a_1,a_2,a_3,\ldots$ satisfies $a_1=1$, $a_2=2$, and $$a_{n+2}=\frac2{a_{n+1}}+a_n\;;$$ find the value of $$\frac{a_{2012}2^{2009}}{2011}$$
0
votes
2answers
83 views

Recurrence relation for words length n

I need to solve following question: "An alphabet consists out of 4 letters a,b,c,d and 3 numbers 1,2,3. Find the recurrence relation for the number of words of length n where no two numbers are ...
1
vote
0answers
39 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
6
votes
2answers
358 views

How to prove $\lim_{n\to\infty}\frac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\frac{1}{2}$?

For any $n\in N$, such $f_{1}=1$, and such $$f_{2n+1}=f_{2n}=f_{2n-1}+f_{n},$$ prove that $$\lim_{n\to\infty}\dfrac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\dfrac{1}{2}.$$
2
votes
0answers
76 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
5
votes
2answers
143 views

Solving a recurrence for a probability?

I came across the following recurrence relation when exploring properties of a certain type of randomized perfect binary tree: $$ T(0) = \frac{1}{2} $$ $$ T(k + 1) = 1 - T(k)^2 $$ (Specifically, ...
3
votes
3answers
77 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 ...
5
votes
3answers
298 views

Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula: $$ a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n $$ This formula is a closed-form expression of a linear ...
1
vote
1answer
65 views

Is this recursion well-defined?

I have a recursion defined by $$ f(n)=\max\{0,-c+pf(n-1)+(1-p)f(n+1)\} $$ with $0.5<p \leq 1$ and $f(0)=R>0$ and $f(m)=0$ for some $m>0$. I am trying to show that $f(n)$ is decreasing in ...
0
votes
4answers
130 views

How do I derive a characteristic equation for this specific recurrence relation?

I have no problems solving recurrence relations with two roots, but I've just encountered one with one root: $c_{n+1} = 3c_{n}+1$ such that $c_{0} = 0$. In my solving process, I suppose I've gotten ...
0
votes
2answers
32 views

Recurrence relations for $a_{n+2}$

I'm trying to figure out how to find closed form equations for recurrence relations. I can find lots of examples for solving equations such as $a_{n} = ca_{n-1} + ca_{n-2}$ and $a_{n+1} = ca_{n} + ...
2
votes
0answers
69 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...
0
votes
1answer
63 views

How to compute the formula of $S_n$

$S_1$=a, $S_2$=b, $S_n$=|$S_{n-1}$-$S_{n-2}$|(n $\ge$3). Can I compute the formula of $S_n$? Thanks in advance.
1
vote
1answer
60 views

Recurrence relation with unequal division

$$T(n) = T(3n/4) + T(n/3) + n$$ Please help me solve this recurrence relation. Somehow even Akra_Bazzi method doesn't seem to work in this case
1
vote
0answers
63 views

looking for explanation behind solution for a 1st order recurrence relation.

In lecture, we covered 1st order recurrence relations and came up with a solution by inspection. I sort of see that we're finding the next term in the sequence by multiplying the initial condition by ...