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

learn more… | top users | synonyms

0
votes
1answer
45 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 ...
4
votes
0answers
89 views

if $(n+1)c_{n}=nc_{n-1}+2nd_{n-1},d_{n}=2c_{n-1}+d_{n-1}$How prove $c_{n},d_{n}$ are integers

let sequences $c_{n},d_{n}$ such $$c_{0}=0,d_{0}=1$$ and for $n\ge 1$,have $$c_{n}=\dfrac{n}{n+1}c_{n-1}+\dfrac{2n}{n+1}d_{n-1}$$ $$d_{n}=2c_{n-1}+d_{n-1}$$ show that $c_{n},d_{n}$ are integers. my ...
0
votes
1answer
124 views

Backwards Recurrence [duplicate]

For $$I_n = \int_0^1 \frac{x^n}{x + \alpha}\,{\rm d}x$$ $\alpha$ constant parameter We know $I_0$ = log[ $\frac{1 + \alpha}{\alpha}$] and we can derive a recurrence formula for $I_n$: $I_n = \frac 1n ...
0
votes
1answer
81 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 ...
1
vote
0answers
35 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
48 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 ...
4
votes
0answers
157 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
3
votes
1answer
25 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 ...
1
vote
0answers
37 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 ...
1
vote
1answer
131 views

How to make recursive computation of $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ stable?

This is homework, so please only hints. We see that the recurrence $$I_n=\frac{1}{n}-\alpha I_{n-1}$$ can be used to compute the value of the integral $I_n=\int_0^1 \frac{x^n}{x+\alpha}\,dx$ ...
2
votes
2answers
105 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. ...
1
vote
2answers
170 views

Question about the “master theorem” of recurrences - no “$b$” term

I'm using the master theorem to find the asymptotic run time of recurrences. For example, for a $T(n) = 4 T(n/5) + n^1$ I find that $T(n)$ is $\Theta(n^1)$, or, simply, constant time, via the set of ...
2
votes
2answers
55 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, ...
3
votes
4answers
117 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: ...
0
votes
2answers
47 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 ...
2
votes
3answers
107 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
0
votes
1answer
332 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 ...
2
votes
0answers
134 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 ...
4
votes
1answer
67 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 ...
1
vote
3answers
103 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( ...
1
vote
1answer
72 views

Prove any $k\in\mathbb{N}$ can be created using sum of $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$

I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition. My attempt was just bad... I've ...
0
votes
1answer
62 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
122 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} ...
2
votes
5answers
106 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
2
votes
1answer
49 views

Recursive Definition for Logarithm

Is it possible to express $\log(n)$ in terms of itself, using only elementary functions, e.g., similar to (the incorrect made-up equation): \begin{equation*} \log(n) = e^n * \log(n - 1) + \sin(n) * ...
1
vote
2answers
47 views

Recursive function definition, how does my teacher arrive at this answer?

I am currently revising for my maths exam in school and there is a section on recursion. The question is explained as follows: $$f(m, n) =\begin{cases} n + 1 &\text{if } m = 0\\ f(m − 1, 1) ...
0
votes
1answer
75 views

How many words can you make with {1,2,3,4} such that difference between 2 letters is 1

Hello and happy new year. I've been struggling with this question and I really need some help. The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write ...
2
votes
5answers
64 views

stuck trying to solve nonhomogeneous recurrence relation

hello and happy new year! I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$. What I did: I ...
2
votes
2answers
85 views

Does there exist an infinite sequence $p_0,p_1,p_2…$ of prime numbers such that $p_k=4 p_{k-1}\pm 1$

$k \in Z^+$ firstly we know that there exists infinetly many primes of the form $4n+1$ by FTA also we see that if we consider finite primes say to $n$ then the recursive formular can be expressed ...
0
votes
1answer
70 views

Solving recurrences with summation factors (Concrete Mathematics)

Chapter 2 in Concrete Mathematics talks about solving recurrences of the form $$a_{n}T_{n}=b_{n}T_{n-1}+c_{n}$$ by reducing them into a sum. The authors multiply both sides by a summation factor ...
3
votes
2answers
85 views

Recurrence equation for $(-1)^k k$

In a project of mine I came across the recurrence relation $$ a_{n+1} = 1 -(n+1)\sum_{k=1}^n{\frac{a_k}{n-k+1}\binom{n}{k}},\quad a_1=2; $$ From calculating the first few terms it seems obvious that ...
4
votes
3answers
162 views

How to solve a 2nd order non-homogeneous linear recurrence?

I have a problem in solving this equation : $x_{n+2} + 3\ x_{n+1} + 2\ x_{n} = 5 \times 3^n $ given that $x_{0} = 0$ and $x_{1} = 1$. I solved the homogeneous associated equation and got $v_{n} = ...
6
votes
0answers
157 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
2
votes
1answer
105 views

The annihilator of $n(2^n)\sin({n\pi \over 2})$

I have to solve this problem: $y(n+2)-y(n)=n(2^n)\sin({n\pi \over 2})$ And I know the annihilator of $n(2^n) = (E-2)^2$, but I don't know how I should find the other part of the annihilator. ...
0
votes
2answers
52 views

representing a recursive difference equation of two variables into one variable equation

suppose the following recursive difference equation ($t$ is time): $$x_t = \frac{a}{1+a}x_{t-1} + \frac{1}{1+a}x_{t+1}$$ where $0<a<1$ is assumed and all values of $a$ at past times are ...
7
votes
3answers
117 views

Help me understanding logic behind limits of recurence relations

I was trying to understand how limits of recurence relations are working. I have one. $$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$ So, from what i know, if this recurence relation has a limit, ...
2
votes
3answers
115 views

Proof that $x^2 - 2y^2 = -1$ has a recurring solution for $x$

I read here about the following variation on Pell's equation: $$ x^2 - 2y^2 = -1.$$ According to Dario Alpern's solver, the equation has infinite integer ...
0
votes
0answers
26 views

Initial conditioins for a recurrence relations

So I have the following recurrence relations which is part of a problem I'm considering: Here, $a_{nx}, b_{nx},c_{nx}$ are the $nth$ derivatives of with respect to $x$? $$\begin{align*}a_{nx} & ...
2
votes
1answer
48 views

What is the relationship between a non homogenous second order difference equation (constant coefficients) and its derivative?

Here's an excerpt of a lecture note I am reading (I've highlighted the beginning of the part that I don't understand): I don't understand how derivative comes into the picture. Here's some context ...
2
votes
1answer
113 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
0
votes
1answer
61 views

Recurrence relation question - check my answers! Basic questions.

I had a chat with a friend about these questions (they are homework questions) , and we argued about the solution. I would just like an outside opinion about my answers: 1) $n \geq 2$ people are ...
0
votes
1answer
88 views

Recurrence relation - simple question. Homework. Permutations with a twist,

I think I solved it but I would love someone to tell me if I'm wrong. the question is as follows: $n$ people are sitting on a bench with $n$ seats. Find a recursive equation that calculates how many ...
2
votes
1answer
73 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
4
votes
2answers
144 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
0
votes
1answer
41 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
2
votes
1answer
43 views

Solving the recurrence $x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$

In my answer over at cstheory.stackexchange.com I set variables according to the recurrence $$x_0=1, x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$$ Wolfram Alpha tells me that apparently the solution to this ...
3
votes
5answers
89 views

Simple functional equation

I have a simple functional equation: $$ \alpha(x) = {1 \over 2}\left[\alpha\left(x - 1\right) + \alpha\left(x + 1\right)\right]\,, \qquad \alpha\left(0\right) = 1\,,\quad\alpha\left(m\right) = 0 $$ I ...
2
votes
1answer
93 views

How find this function $f(2^m)=?$

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$ and Find $f(2^m),m>2,m\in N$ My try: let $n=3$ ,then we have ...
0
votes
3answers
158 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
1
vote
1answer
82 views

Finding explicit formula for recurrence relation?

What would a explicit formula for this sequence? a_k = a_(k-1)/k? The way I find explicit formula is to write out some terms but this time it's not working.. I'd appreciate your help!