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

learn more… | top users | synonyms

1
vote
4answers
57 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
31 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
22 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
28 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
28 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
41 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
380 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
31 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
32 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
145 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
35 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
34 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
63 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
12 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
118 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 ...
0
votes
0answers
32 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
33 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
50 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 ...
4
votes
1answer
35 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
213 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
154 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
65 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
49 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
28 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
35 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
26 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? ...
1
vote
2answers
20 views

Solving a recurrence equation that yields polynomials

I am trying to solve the following recurrence equation: $$ T(n) = kT(n - 1) + nd $$ I have expanded the first 4 values ($n = 1$ was given): $$\begin{align} T(1) & = 1 \\ T(2) & = kT(2-1) + ...
1
vote
1answer
27 views

constructing the matrix associated with a recursive function

This problem arrives from the Tower of Hanoi problem. We know that the least number of moves required to move the tower from one point to another is $2^n- 1$ where $n$ is the number of discs in the ...
2
votes
1answer
31 views

Find all sequences that satisfy the recurrence relation

Find all sequences that satisfy the recurrence relation $$u_n\cdot (u_{n+1})^2-u_{n+1}-u_n+1=0, \text{with }u_0=1$$ My try First, we find $u_1$, which follows $u_0=1$. $u_0\cdot ...
1
vote
1answer
31 views

How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same. Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
1answer
24 views

Solving recurrences for Big-Theta bound

So I am working on my assignment and have gotten stuck. For previous questions I was able to use Master Theorem to get $\Theta$, but can't use the theorem for this question.. I know to get $\Theta$ I ...
1
vote
2answers
42 views

Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

I have the following equation: $$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$ A little investigation: $T(2^1) = 1 + 2d$ $T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$ $T(2^3) = T(2^2) + ...
1
vote
1answer
61 views

Find $a_{n}$ from a convolution formula

Suppose that $c_{n}$ satisfies the recurrence formula below: $c_2=\alpha$, and $$c_{2n}+c_{2n-2}=\frac{(\alpha)_n}{n!},n\geq2.$$ were $(\alpha)_n = \alpha(\alpha-1)·\cdots·(\alpha-n+1)$ and $\alpha$ ...
6
votes
1answer
71 views

A proof by strong induction that $a_n\le3^n$ where $a_n=a_{n-1}+a_{n-2}+a_{n-3}$

I am not sure whether this is right. Can anyone verify, whether this proof is valid? Thanks! Define a sequence $\{a_n\}_{n\ge0}$ as follows: ...
1
vote
1answer
55 views

Recursive Solution to Interest with Monthly Deposits

I open an account at a bank with 1% interest compounded monthly. I'm adding $100 to it at the beginning of each month (starting with month 1). (a) Set up a recurrence relation for the amount in the ...
1
vote
2answers
77 views

Limit of $a_{n+1}=\frac{2a_n^3}{1+a_n^4}$

Let $a_1$ be real, and define $$a_{n+1}=\frac{2a_n^3}{1+a_n^4}$$ How can I prove that this $\{a_n\}$ to have limit. I find it is hard to track. What I can do is just when $a_1=1$ then $a_n=1$; when ...
0
votes
2answers
49 views

Recurrence Relation $T(n) = T(\frac{n}{2}) + \sqrt{n}$

$T(n) = T(\frac{n}{2}) + \sqrt{n}$ and $T(1) = 1$. Assume $n = 2^k$. $$T(2^k) = T(2^{k-1}) + 2^{k/2}$$ $$T(2^{k-1}) = T(2^{k-1}) + 2^{k/4}$$ ... $$T(2) = T(1) + 2^{k/k} $$ $$T(1) = 1$$ I'm just ...
0
votes
1answer
34 views

Advanced Recurrence Relations

I have to find a close form of the following Recurrence Relations. $P_{t+1} = P_t - \frac{p}{t}P_t$ With $P_{i+1}=\frac{p}{i}$, for some $i < t$. I tried the unfolding method on Knuth, but it ...
0
votes
1answer
35 views

consecutive heads

If a coin is tossed 3 times, there are 8 possible outcomes: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT In the above experiment we see 1 sequence has 3 consecutive H, 3 sequences have at least 2 ...
0
votes
0answers
11 views

difference equations/inequalities in two variables without constant coefficients

I have a linear inhomogeneous difference inequality with variable coefficients. I was wondering if there are any general methods available for solving it. The case where the inequality is replaced by ...
1
vote
2answers
48 views

Recurrence Question about $T(n) = T(\frac n2) + nlog(n)$

So I've been working on this recurrence equation and I'm stumped at the end. $T(n) = T(n/2) + n\log(n);\: T(1) = 1;\: n = 2^k$ and log is base $2$. $T(2^k) = T(2^{k-1}) + 2^k\times \log(2^k)$ ...
0
votes
1answer
30 views

use substitution method to prove an equation is in O(n log2 n)

I am trying to prove that the equation: T(n) = 2T((n/2) +17) + n is O(n log_2(n)) I have to do this by using substitution ...
1
vote
1answer
25 views

Recurrence Algorithms

What is the best method of solving non standard recurrence algorithms? In particular something like the following: What would be it's tight bound in Theta notation? $$ n \in N\\ T(n) = \sqrt{n} \; ...
1
vote
2answers
53 views

How do you solve these recurrence relations for a closed form?

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of ...