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

learn more… | top users | synonyms

4
votes
2answers
27 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 ...
0
votes
1answer
40 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
27 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
38 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
25 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
18 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
21 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
19 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
23 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
23 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
30 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
18 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
23 views

Recurrence equation of $\displaystyle T(n) = T({n \over 2}) + dn\log_2(n)$

I have the following equation: $$T(n) = T({n \over 2}) + d\times n\times \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
54 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$ ...
5
votes
1answer
53 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
48 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
75 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
47 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
30 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
34 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
9 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
47 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
27 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 ...
0
votes
1answer
29 views

How do you typically prove recurrence relations?

The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to ...
1
vote
1answer
15 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
1
vote
0answers
64 views

How do I derive this recursive function?

I have a function $S_t = a*Y_t+(1-a)*S_{t-1}$ Where $a\in (0,1)\cap \mathbb{Q}$, $t$ represents a unit of time and $Y_t$ is the value at a time period $t$ I am trying to find $dS_t \over dt$ I ...
0
votes
3answers
109 views

How would I show that Tn=3^n + 2 is a solution to the recurrence?

Would anyone be able to help me or give me some advice on the following problem: Consider the recurrence with $T_0 = 3$ and $T_{n+1} = 3T_n - 4$ for all $n \in \mathbb{N}$. How would I show that ...
1
vote
1answer
23 views

How can I solve the particular solution of the following recurrence (recursive) relation?

Having $a_n = 3a_{n-1} + 2a_{n-2} + 3·2^{2n-1}$ $a_1 = 12$ $a_0 = 0$ I solved the homogeneous part and got: $a^{{h}}_n = 1/12·2^n - 1/12·1^n$ This is the particular solution that I need to ...
1
vote
0answers
23 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
3
votes
2answers
67 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
1answer
28 views

How do I solve this recurrence relation

How do I solve the following recurrence relation: T(n)=4T(n-1) - 3T(n-2) I tried using substitution but failed as I was unable to find any "general" i-th term ...
3
votes
3answers
192 views

Closed Form of Recursion

Given that $a_0=2$ and $a_n = \frac{6}{a_{n-1}-1}$, find a closed form for $a_n$. I tried listing out the first few values of $a_n: 2, 6, 6/5, 30, 6/29$, but no pattern came out.
1
vote
1answer
27 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
0
votes
1answer
29 views

Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
0
votes
0answers
14 views

count the permutation which have $k$ maxima

I need some help for the following homework question. A permutation $P (\pi_1\pi_2...\pi_n)$ of {$1,2,...,n$} is given. We say that $j$ is a maxima of $P$ whenever $\pi_j$>$j$. How can I find ...
0
votes
1answer
57 views

How do I say that an infinite-state Markov chain is positive recurrent? [closed]

I run into this Markov chain while I'm doing my research, and I can't figure out how to find the condition under which this Markov chain is positive recurrent. This is a brief scenario of my ...
1
vote
1answer
28 views

$g(n)=\sum_{i=0}^{n-1}g(i)g(n-i-1)$, and $g(0) = 1$, so which is $g(n)$?

I have an equation that: $g(n) = g(0)g(n-1)+g(1)g(n-2) + ... + g(n-2)g(1)+g(n-1)g(0)$ And I also know that $g(0)=1$. How can I derive the close form of function $g(n)$ ?
1
vote
2answers
234 views

Help solving a recursion function T(n) = T(n-2) +3

I have the following recursion function: $T(1) = 0$ $T(n) = T(n-2) + 3$ where n is odd integers I know the closed form of this is: $T(n) = \frac{3n-3}{2}$ but this was purly by guessing. Is it ...
0
votes
1answer
17 views

Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
1
vote
2answers
19 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
0
votes
1answer
65 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
2
votes
5answers
26 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
0
votes
1answer
29 views

recursive definition of the relation

Give a recursive definition of the relation greater than on N X N using the successor operators s? I answered this question throw this way: Basis: o ∈ N X N recursive step: if n ∈ N X N, then s(n) ∈ ...
0
votes
1answer
21 views

Prove boundedness of recurrence relation

For a number sequence $\{y_n\}$ we know that $y_{n+1} = 2y_n-y^2_n$ If: $0<y_0<1$ show that $0<y_n<1$ for all integers $n>0$ I've tried solving the recurrence relation, but I couldn't ...
0
votes
1answer
33 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
2
votes
3answers
82 views

Solving a recurrence relation of second order

I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$ $x_2 = 2(x_1-x_0)+x_1$ $\begin{align} x_3 = ...
0
votes
2answers
44 views

Closed form formula for the given product

I'm working on a recurrence which give me the following solution: $$ f(n)=(2+1)(2+\tfrac12)(2+\tfrac13)\cdots\left(2+\tfrac1{\lg(n)}\right) $$ so for $n=16$, $f(n)$ is just like: $$ ...
2
votes
1answer
58 views

Solving the recursion $y_n=2ny_{n-1}$ with Wolfram|Alpha

This is blowing my mind away ... this should be easy stuff! Starting with the recursive formula $y_n=2n*y_{n-1}$ where $y_1=5.$ I'm trying to come up with a formula for the series { 5, 20, 120, 960, ...