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

learn more… | top users | synonyms (2)

2
votes
2answers
266 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 ...
1
vote
2answers
73 views

How to find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / b(x)$?

Consider the sequence $c_0, c_1, c_2,\ldots$ satisfying $c_i =2\cdot 3^i − i^2\cdot(−1)^i$. Let $c(x) = c_0 + c_1x + c_2x^2 + \ldots$ Find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / ...
5
votes
0answers
68 views

Right way to solve this reccurence relation?

I am not that good in mathematics , I have solved many simple relations. But I am not be able to solve the following. This is not a homework. I found it during analysis of a program. ...
1
vote
2answers
116 views

Recurrence equation

Given the following recurrence equation: $T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$ How would you set this equation up in order to allow you to solve it using telescoping? Thanks in advance.
1
vote
1answer
78 views

How to find algebraic simplification for recurrence relation with closed-form solution, specifically for the Lucas-Lehmer primality test

I have a question based on the section Proof of correctness in the article Lucas-Lehmer primality test, see following link. ...
1
vote
2answers
58 views

solve the following recurrence exactly.

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)+t(n-4)&\text{otherwise.}\end{cases} $$ Express your answer as simply using the theta notation. I don't know where to go ...
2
votes
3answers
115 views

How to tackle a recurrence that contains the sum of all previous elements?

Say I have the following recurrence: $$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$ where $n = ...
3
votes
2answers
91 views

recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ ...
0
votes
1answer
65 views

Prove that the recurrence is true [duplicate]

I am working on an assignment question, and am having trouble moving ahead. The question is as follows: Let the total number of bit strings with three consecutive zeros be $t_n$. Prove for $n \ge ...
0
votes
1answer
119 views

Using induction to prove a general form from a recurrence relation

I have the recurrence relation: $a_{n+2} = \dfrac{-a_{n}}{(n+2)(n+1)}$. I have done some work to identify that two cases emerge: one is n is positive, and one if n is negative. If n = 2m (even) ...
2
votes
2answers
119 views

What is the asymptotic bound for this recursively defined sequence?

$f(0) = 3$ $f(1) = 3$ $f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$ Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not ...
0
votes
1answer
56 views

Master's theorem applicability.

I have to find out if the following recurrence can be solved with the master theorem: $$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$ I have figured that, here, I have the third case because ...
1
vote
1answer
63 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
1
vote
1answer
55 views

How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
0
votes
1answer
54 views

Master Theorem Question

I need to solve the following: $T(n)=T(n-1)+8$ I've tried doing $a=1$, $b=-1$, and $d=8$ but $\log_{-1}1$ doesn't make sense. Any suggestions?
0
votes
1answer
41 views

Recurrence relation for $n$ digit numbers not containing '$20$'

How many n digits base $3$ numbers do exist such that they never contain pattern '$20$'? (first find a recurrence relation)
2
votes
0answers
102 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
0
votes
1answer
27 views

Characteristic equation of a difference equation indicates the function behavior

For the characteristic equation $a_2 \lambda^2 + a_1 \lambda + a_0 = 0$ of the difference equation $a_2 x_{n+2} + a_1 x_{n+1} + a_0 x_n = 0$, I remember there is a way to indicate if the function of ...
1
vote
2answers
2k views

Recurrence $T(n)=T(\sqrt n) + \Theta(\log(\log(n))$

I need to find the bounds of the above recurrence . I've tried the following however got stuck : $T(n)=T(\sqrt{n})+Θ(\log(\log(n) )=$ $n=2^m,\quad m=\log(n)$ $T(2^m)=T(\sqrt{2}^m ...
1
vote
4answers
42 views

Identity for this recursive relation with multiple terms

I have a recursive relation algorithm which is defined as follows: $$F_n = 3(F_{n-1} - F_{n-2}) + F_{n-3}$$ $$F_0 = 0$$ $$F_1 = 1$$ $$F_2 = 4$$ From calculating the first few values, I know this is ...
1
vote
2answers
52 views

How do we solve the exact recurrence for $T(1) = 1, T(n) = 3T(n - 1) + 2n + 2$ for $n > 1$?

This looks like an exponential recurrence due to the 3 behind $T$, but I'm not sure how to formally solve for $T(n)$ without $T$ on the righthand side.
3
votes
3answers
173 views

Why does this recurrence relation generate a sinusoidal curve?

I came across the following coupled recurrence relation while watching this video called Media for Thinking the Unthinkable: $a_{n+1} = a_n - 0.069\cdot b_n$ $b_{n+1} = b_n + 0.069\cdot a_{n+1}$ ...
0
votes
1answer
34 views

How do we solve a tight big-O bound for the recurrence $T(n) = T(n^{2/3}) + 1$?

The big-O bound seems largely governed by how many times we can take the input $n$ by the $\frac{2}{3}$ power until it reaches some constant like 1. How do I start formalizing this problem in math ...
2
votes
1answer
39 views

Four or More Heads in a Coin Toss

How would one write a recursion for the number of ways to get 4 or more heads in a row in 10 tosses of a coin? Would it suffice to use the recursion H(n)=H(n-1)+H(n-2)+H(n-3)+H(n-4) for the number of ...
0
votes
1answer
65 views

Can every recurrence relation be solved?

Motivation A possible way to solve an ODE is to express the solution as: $y= \sum_{n=0}^\infty a_nx^n$. We substitute in the ODE and then calculate the coefficients $a_n$. For example, $y''+y=0$ ...
0
votes
2answers
117 views

Combinatorics - Check my answer, sitting order, round table.

$n$ people are sitting at a round table with $n$ seats at a restaurant. The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 ...
0
votes
1answer
156 views

Plot of recurring system in MATLAB, Lozi map

I need to write this recurring system in MATLAB $$ x_{n+1}=1-a|x_n|+y_n$$ $$ y_{n+1}=bx_n $$ and take its plot for every $x_i,y_i$,with let's say a=1.4 and b=0.7. $$$$This is the Lozi map. And this ...
0
votes
1answer
93 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
3
votes
3answers
96 views

Recurrence $f(a,b)=f(a,b-1)+2f(a-1,b-1)$

Consider the recurrence relation $$f(a,b)=f(a,b-1)+2f(a-1,b-1)$$ for integers $a,b\geq 2$, where $f(a,b)=1$ if $a=1$ or $b=1$. Is it possible to find a closed form for $f(a,b)$?
3
votes
1answer
62 views

Finding Determinants Recursively

From the MIT OCW Linear Algebra (18.06) final exam, question 9: For square matrices with 3's on the diagonal, 2s on the diagonal above, and 1s on the diagonal below: $$A_1=\begin{pmatrix} 3 ...
9
votes
1answer
322 views

Recurrence equation similar to a geometric progression

I have the following recurrence relation: $$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$ with $k \geq 0$, a fixed constant. I know that when $k=0$, we have: $$T(i) = \sqrt{T(i-1) T(i+1)},$$ which ...
1
vote
0answers
46 views

Recurrence of a function

Consider the following recurrence: $$ T(n) = 2T(n/2)+n\lg n$$ Let’s use a base-case $T (2) = 2$ and let’s assume $n$ is a power of $2$. (a) “guess and prove by induction” method, considering the ...
2
votes
3answers
49 views

Help with recurrence relation

It 's been a long time since I touched this kind of math , so please help me to solve the relation step by steps : $V_k = (1+i)*V_{k-1}+P$ I know the answer is $V_k = (P/i)*((1+i)^k-1) $ Thanks ...
3
votes
1answer
27 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
3
votes
2answers
136 views

A proof using $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$

Please How can I use $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$ to prove $\sum_{i=0}^{n}{(-1)^i\dbinom{n}{i}y(i)}=(-1)^n\Delta^ny(0)$ and hence to evaluate ...
7
votes
2answers
2k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
1
vote
0answers
42 views

Algorithms: Recurrence

Here's a problem that I am struggling with... If two algorithms A and B both solve the same problem. On an input of size $n$ Algorithm $A$ breaks it into $5$ pieces of size $n/2$, recursively solves ...
2
votes
2answers
110 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
2
votes
2answers
57 views

Question with recurrence - Check my answer and suggest better ideas

Every morning when he gets up, Oria leaves the house for a walk. he walks exactly $n$ steps. He can walk only forward, right, or left, and he will never turn left immediately after he turned right, ...
1
vote
3answers
131 views

$W_n=\int_0^{\pi/2}\sin^n(x)\,dx$ Find a relation between $W_{n+2}$ and $W_n$

Set $$W_n=\int_0^{\pi/2}\sin^n(x)\,dx.$$ Compute $W_0$ and $W_1$. Find a relation between $W_n$ and $W_{n+2}$ and deduce a formula for $W_n$. What I have so far is: $$W_{2k}=\frac{1}{2^k}\left( ...
3
votes
4answers
236 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
2
votes
2answers
525 views

Analysis of algorithms and recurrence relations

Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding ...
1
vote
0answers
25 views

Difference equation - counting problem

I need to to define difference equation for following problem and solve that equation using generating function. Border of length 10cm is made of small bricks (10cm long) and large bricks (20cm ...
2
votes
0answers
139 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
0
votes
2answers
49 views

Recurrence relation - Show that a sum of a sequence is zero

We are given the following sequence: $f(n)=4f(n-1)-5f(n-2)$, $f(0)=f(1)=a$ where $a$ is some value in $\mathbb C$. We are asked to show that $$\sum_{n=0}^{\infty}\frac{f(n)}{3^n}=0$$ First thing I ...
0
votes
1answer
696 views

Summation of logarithmic series

I am solving a recurrence relation and it requires me to sum the following series upto $\log{n}$ terms - $1/\log(n) + 1/\log(n/2) + 1/\log(n/4)$..... The base in each term is $2$. Any help on ...
1
vote
1answer
35 views

Difference equation formula $\sum a^t = \frac{a^t}{a-1}$.

As I explain below, this question was originally posted by user YYG, but then deleted. I am reposting the question (from memory) and I will answer it myself below. Question: In Difference Equations ...
4
votes
1answer
78 views

Find recursive forumula for integrals

I have to find recursve formulas for solving the following two integrals. The assignment tells one to find an Expression that leads from the calculation of $\dfrac{I_{2n}}{I_{2n+1}}$ to the ...
0
votes
1answer
111 views

Period of recurrence relation mod p

For a recurrence relation like $$f(n)=((k-2)*f(n-1)+(k-1)*f(n-2) )\bmod p$$ with initial conditions .This recurrence holds for n>=4 $$\begin{align}f(1)&=k \bmod p\\ f(2)&=k*(k-1) \bmod ...
4
votes
1answer
135 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...