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

learn more… | top users | synonyms

2
votes
2answers
61 views

Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Sorry about the formatting of the title I'm not sure of the codes to make it look better. I need to find the recurrence relation of the following: $$T(0) = 1$$ $$T(n) = ...
1
vote
0answers
38 views

Non-recursive closed-form of the coefficients of Taylor series of the reciprocal gamma function

The reciprocal gamma function has the following Taylor series. $$\frac{1}{\Gamma(z)}=\sum_{k=1}^{\infty}a_kz^k,$$ where the $a_k$ coefficient are given by the followint recursion. $a_1=1$, ...
1
vote
4answers
98 views

Prove sequence is Cauchy.

Prove the sequence $\{a_i\}$ defined by $a_1=1 \text{ and } a_{i+1} = 1 + \frac{1}{a_i}$ is Cauchy. And prove it converges to $\sqrt{2}$. I want to show $\lim\limits_{n\to\infty}(a_{i+1}-a_i)=0$ for ...
5
votes
2answers
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
1
vote
0answers
31 views

Complicated 2-variable recurrence

I am analyzing some kind of construction for which size satisfies the following recursion: $P(n,k)=\frac{k}{2}\log \frac{k}{2} + 1 + \frac{n}{2} + P(\frac{n}{2},k) + P(\frac{n}{2},\frac{k}{2})$ ...
1
vote
1answer
36 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
0
votes
1answer
46 views

Limit of a sequence defined by recursive relation : $ a_n = \sqrt{a_{n-1}a_{n-2}}$

We're given a sequence defined by the recursive relation: $$a_n = \sqrt{a_{n-1}a_{n-2}}$$ $a_1$ and $a_2$ are positive constants. We have to show the following: The sequences $\{ b_n \} = \{ ...
2
votes
1answer
39 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
3answers
37 views

This recurrence relation will evaluate to?

T(n) = 2T(n-1)+n, n>=2 T(1) = 1 What will this recurrence relation equation evaluate to ? I used substitution method and found out that this relation takes the form 2^k T(n-k) + 2^(k-1) * ...
1
vote
0answers
18 views

Solving a recurrence with a term $T(\frac n 2 + 2)$

I'm stuck trying to solve the following recurrence: $$\begin{align*} T(n) &= 4T(\frac n 2 + 2) + n : n > 8\\ T(n) &= 1 : n \leq 8 \end{align*}$$ In particular, I'm not sure how to deal ...
0
votes
0answers
4 views

About Laguerre Recurrence Relation from Gram-Schmidt

I wonder how to deduce Laguerre Recurrence Relation from Gram-Schmidt onthogonalization process applied to the monomial basis Thanks
0
votes
0answers
13 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
1answer
46 views

Help with using Master Theorem on Floor/Ceiling Functions [closed]

I have to use the master theorem to find the asymptotic growth of this function in Big-theta notation. T(x) = T(⌈x/4⌉) + T(⌊x/4⌋) + √x How should I approach this ...
1
vote
1answer
62 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
3
votes
4answers
92 views

Recurrence relation $x_0=1, x_n=p x_{n+1} + q x_{n-1}$

I have the following recurrence relation: $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1} \text{ for }n=1,2,3,...$$ where $0<p=1-q<1$ and $0 \leq x_n \leq 1$. Edit: Sorry for the lack of context. But I ...
0
votes
1answer
18 views

Substitution method for solving recurrences piece wise function

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$
0
votes
0answers
22 views

Recurrences with modulo

Is there any specific way to solve recurrence of form (example): $$f(x) = (a \cdot f(x-1) + c) \bmod{r} $$ (when recurrence involves modulo). For recurrence without modular arithmetic I could use ...
1
vote
2answers
65 views

Determine whether $A215928(n)=G_n$.

Let $G_0=1$ and $G_{n+1}=F_0G_n+F_1G_{n-1}+\cdots+F_nG_0$, where $F_n$ is the $n$th term of the Fibonacci sequence, i.e., $F_0=F_1=1$ and $F_{n+1}=F_n+F_{n-1}$. Let $P_0=P_1=1,\ P_2=2,$ and ...
1
vote
4answers
62 views

Is this recursively defined sequence decreasing? $x_{n+1}={1\over{4-x_n}}$, $x_1=3$.

This is part of a larger problem: Prove that the sequence defined by $x_1=3$, $x_{n+1}={1\over{4-x_n}}$ converges. I want to show that it is bounded below (by $0$ or something) and that it is ...
1
vote
3answers
32 views

Showing that a sequence $a_n$ is a solution of the recurrence relation

I'm having some trouble with showing that a sequence $a_n$ is a solution to the recurrence relation $a_n = -3a_{n-1} + 4a_{n-2}$. (See image below). The sequence $a_n$ that is given $= (-4)^n$ . I'm ...
1
vote
2answers
30 views

How to analyze convergence of non-linear difference equation (recurrrence relations)

I've a couple of functions, such as: $Y(t+1)=2-\ln(Y(t))$ $Y(t+1)=(Y(t))^{-2}$ $Y(t+2)=e^{-Y(t)}$ and I need to analyze stability and convergence. No problem with stability, but I can't figure out ...
1
vote
1answer
35 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
3
votes
0answers
30 views

How to work with a recursive function with 2 recursive instances?

In class, we figured out how to find the closed form of a recursive definition through the "basic 5 steps method". Example function T(n): If n = 1, T(1) = 1 If n > 1, T(n) = T(n-1)+1 Step 1: ...
0
votes
1answer
44 views

Finding recurrence relation on a problem

I need a little bit help finding a recurrence relation. So it goes like this: "A one-sided pavement is being made with tiles that come in 5 different colors. There are 3 light colors (light-yellow, ...
19
votes
1answer
396 views

Infinite staircase to a circle

Suppose you start at $(0,0)$ on the unit disc and repeat the following procedure again and again: Face east and walk half-way to the circumference. Face north and walk half-way to the circumference. ...
1
vote
2answers
34 views

How do I solve this recurrence relation?

Given a recursive relation $$a_n = \begin{cases} (1 - 2b_n)a_{n-1} + b_n, & n > 1 \\ \frac{1}{2}, & n =1 \end{cases} $$, how can I expression $a_n$ in term of $b_i, i \in \{1, 2, \dots ...
1
vote
1answer
20 views

Checking recurrence relation

Is there a way to check my recurrence relation, so I can confirm I did it correctly? $a_k = -4a_{k-1} -4a_{k-2}$ with $a_0 = 0$ $a_1= -1$ My answer: $a_n = 0(-2)^n - ½n(-2)^n$
1
vote
1answer
34 views

How do I use complete induction here?

Suppose currency consists of 3 and 4 cent coins. Suppose you want to buy an item that is worth 9 cents. Show that if you have an unlimited number of 3 and 4 cent coins you can buy anything greater ...
0
votes
0answers
13 views

Maxima of a recurrence

The following recurrence has a maxima around $k = \lceil \log_d{n}\rceil$, where $n > 0$, $d > 3$: $$b(n,k) = {b(n-1,k-1)\over {d^{k-1}}} + (1-{1\over {d^{k}}})b(n-1,k)$$, where $0 \le k \le ...
0
votes
0answers
34 views

combinatorial maths recurrence relations for distribution of N objects into 3 different boxes

Given N balls which are red, green or blue in color.And three boxes R,B,G.In how many ways these N balls can be distributed so that box R contains atleast r no of red balls, B contains atleast b no of ...
6
votes
1answer
147 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
0
votes
0answers
38 views

Solving a linear recurrence with unknown changing coefficient.

I'm stuck on how to solve this recurrence (if it can be solved?) Any help or tips would be greatly appreciated. \begin{equation} x_n=a_nx_{n-1}-x_{n-2} \end{equation} with $x_1=-1$ and $x_2=-a_2$ ...
2
votes
2answers
36 views

2 element subsets of n elements?

the question is as follows: Give a recursive definition for the number of $2$-element subsets of $n$ elements. We started working this out in class and here is where we got too: -if $n = 0$, then ...
2
votes
1answer
64 views

Do we have to claim it? If so, at which point?

I have to solve the recurrence relation $$T(n)=\left\{\begin{matrix} 3T\left (\frac{n}{4} \right)+n & , n>1\\ 1 &, n=1 \end{matrix}\right.$$ and prove by induction that the solution I ...
1
vote
1answer
14 views

Identifying R1 and R2 when solving Recursion relations

We are learning to solve recursion relations. When I get this step, does it matter if I define $r_1$ as 5 or 2 in this example?
2
votes
3answers
124 views

Recurrence relation problem

If $a$ is a sequence defined recursively by $a_{n+1} = \frac{a_n-1}{a_n+1}$ and $a_1=1389$ then can you find what $a_{2000}$ and $a_{2001}$ are? it would be really appreciated if you could give me ...
-1
votes
0answers
36 views

Inductive definition on a sequence

I have a question which goes like this: "Show the inductive definition for the sequence {$a_n$} if $a_n = 5 + 7n$ and $n = 0, 1, 2, 3, 4, ...$ I was wondering given the formula to find $a_n$ is it ...
1
vote
1answer
34 views

Power Series of Recurrence

Let n be a Natural number. Define $\ S_n $ to be the set of compositions of $\ n $ where no part is equal to 2, and let $\ a_n = |S_n| $. It is trivial that: $$ a_n = [x^n] \frac{1-x}{1-2x+x^2-x^3} ...
2
votes
3answers
52 views

How to derive the closed form of this recurrence?

For the recurrence, $T(n) = 3T(n-1)-2$, where $T(0)= 5$, I found the closed form to be $4\cdot 3^n +1$(with help of Wolfram Alpha). Now I am trying to figure it out for myself. So far, I have worked ...
5
votes
1answer
36 views

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: ...
6
votes
1answer
225 views

Recursion relation of fourth order Runge-Kutta method applied on system

I'm trying to apply the Gauss-Legendre method of fourth order (as Runge-Kutta method) on the following system of equations $$\left\{ \begin{matrix} \dot{a} =& -b \\ ...
2
votes
4answers
164 views

Amateur Math and a Linear Recurrence Relation

I haven't received a formal education on this topic but a little googling told me this is what I am trying to find. I would like to put $$ a_n = 6 a_{n-1} - a_{n-2} $$ $$ a_1 =1, a_2 = 6 $$ into its ...
2
votes
3answers
68 views

Why do we set $u_n=r^n$ to solve recurrence relations?

This is something I have never found a convincing answer to; maybe I haven't looked in the right places. When solving a linear difference equation we usually put $u_n=r^n$, solve the resulting ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
-1
votes
1answer
51 views

solving recurrence relation.

Solve the following recurrence relation $$P(1)=2$$ $$P(n)=2P(n-1)+2^n\cdot n$$ for $n\ge 2$ I know I need to expand to look for a pattern but it's not clicking for me. I don't see the pattern that ...
1
vote
1answer
29 views

Solving a recurrence using the Master Theorem where $f(n) = log(\log n)$

I have the recurrence $$T(n) = 3\,T(n/2) + \log(\log n)$$ I take $a = 3$, $b = 2$ and $f(n) = \log(\log n)$. I also have $\log_2 3 = 1.585$. I'm not sure how to approach a log inside of a log. Would ...
0
votes
2answers
41 views

prove $S(n) \leq (5/2)^n$

I've been flipping through my math book for nearly 5 hours working on these recursive problems and it's just not clicking. I have a recusrive sequence $S(0) =1$ $S(1)=2$ $S(n) = 2S(n-1) +S(n-2)$ ...
1
vote
0answers
31 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
1
vote
1answer
38 views

Expanding a recurrence relation with a summation involved

Question: $(10)$ Solve the recurrence in asymptotically tight big Oh function; $$t(n)=n+\sum_{i=1}^kt(a_in),$$ for the two cases (a) where $\sum_{i=1}^k a_i < 1$, and (b) where ...
2
votes
0answers
30 views

How to solve a first order inhomogenous recurrence relation?

I have a recurrence relation for a fund that starts a 50 million, 6 % interest every year, and an outtake of 2 million/year. How to find out a solution for what funds exists after n years? ...