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

learn more… | top users | synonyms (2)

1
vote
0answers
23 views

Upperbound for quadratic recurrence equation

I have a quadratic recurrence equation $\forall n \ge 2$ of the form $$ f(n)=\sum_{l=1}^{n-1} f(l)f(n-l), $$ with the initial condition $f(1) =1$. The first few terms of the series are given by ...
1
vote
1answer
29 views
0
votes
1answer
54 views

How to find the general solution of the difference equation [closed]

Take this as an example. Wondering if someone can elaborate their ideas. Thanks a lot!
2
votes
0answers
22 views

Solving recurrence relation, no clue how to approach

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{3n}{4}\right)+T\left(\frac{n}{\log n}\right)+C\cdot{n}\log\log n$$ The answer should be $T(n)=\Theta(n \log\log n)$ ...
0
votes
0answers
44 views

List step by step instructions to turn a properly colored pie of j sectors into a properly colored pie of j+1 sectors

A circular disk is cut into n distinct sectors, each shaped like a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
1
vote
2answers
27 views

Solve the following recurrences using backward substitutions: [closed]

Solve the following recurrences using backward substitutions: $x(n) = 3x(n-1)$, for $n > 1$; $x(1) = 4$
3
votes
2answers
33 views

Compute the limit of a recursively defined sequence in terms of its initial values [duplicate]

Consider the sequence $\{ a_n \}$ defined recurisvely in terms of $a_1$ and $a_2$ by $$ a_{n+1} = \frac{a_n + a_{n-1}}{2} $$ for $n \geq 2$. Assuming this sequence converges, find the limit in terms ...
0
votes
0answers
14 views

Citation Resource? Discrete Variation of Parameters

I have a colleague that needs a citation resource for variation of parameters in the discrete setting when solving non homogeneous linear recurrence relations. I have tried googling for it, but I'm ...
0
votes
0answers
20 views

Solving recurrence relation $T(n)\le T(0.9n)+T(0.2n)+O(n)$

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{9}{10}n\right)+T\left(\frac{1}{5}n\right)+\text{O}(n)$$ According to book it should be that $T(n)=\text{O}(n^2)$. I ...
1
vote
1answer
43 views

Relation between two sequences or summations

Let us define two sequences \begin{equation} G_{n}=\sum_{i=1}^n a^{-i}t_{i-1} \end{equation} and \begin{equation} g_{n}=\sum_{i=1}^n t_{i-1} \end{equation} where $a$ is an integer and $t_n$ is an ...
2
votes
4answers
55 views

Solving Recurrence Relation problem

I am trying to solve the recurrence relation: $$G_n = \frac{1-G_{n-1}}{4}$$ $$G_0 = 0$$ $$G_1 = \frac{1}{4}$$ I am told that the answer is $$G_n = \frac{1}{5}\left(1+\left(\frac{-1}{4}\right)^{n+1}\...
0
votes
2answers
41 views

Linear Recursion with backtracking

I have been trying to solve this question for hours. But can't seen to figure out how to solve it by backtracking. Is my current step correct? May I get some help how to continue and derive the ...
1
vote
1answer
24 views

Binary string function with unique one-counting prefixes

I'm looking for a partial function $f$ from binary strings to natural numbers such that the following holds ($x$ and $y$ always represent binary strings, $\epsilon$ is the empty string, $H(x)$ is the ...
2
votes
1answer
42 views

Proving for sequences that “$K$th difference is constant” implies "$K$th degree polynomial

Here's something that strikes me as clear but I couldn't prove it (I must be missing something simple): Take a sequence $\{ a_n \}$. The first differences are the sequence $\{a^{(1)}_n\}$ where $a^{(...
0
votes
0answers
16 views

Is a subsequence of linear recurrence also recurrence? [duplicate]

Let $u=(u(0),u(1),...)$ be a linear recurrence over some commutative ring $R$: $$u(i+m)=c_0u(i)+c_{1}u(i+1)+\cdots+c_{m-1}u(i+m-1),$$ where $i\geq0$ and $c_0,...,c_{m-1}\in R$ The question: is the ...
0
votes
0answers
60 views

Recurrence relation by linear algebra.

Got stuck trying to solve this recurrence relation found over here using my favourite set of tools in linear algebra. Question, find analytic or algebraic expression for $a_n$: $$a_n = n a_{n-1} + n(n-...
3
votes
1answer
58 views

Find closed formula for $a_{n+1}=(n+1)a_{n}+n!$

$a_{n+1}=(n+1)a_{n}+n!$ where a0=0 and n>=0. To get the closed form, I'm trying to find an exponential generating function for the above recurrence, but it doesn't seem to be very nice. Am I going ...
0
votes
0answers
18 views

How to solve difference equation?

I have following differential-difference equation, and i was wondering if analytical solution to this is possible. $\frac{\partial C(r,N,t)}{\partial t} = C(r-1,N-1,t) a-C(r,N,t) b + C(r+,N+1,t) c + ...
3
votes
1answer
58 views

Find closed formula for the recurrence $a_{n}=na_{n-1}+n(n-1)a_{n-2}$

$a_{n}=na_{n-1}+n(n-1)a_{n-2}$ where a0 = 0, a1=1, and n >= 2. I found an exponential generating function for this recurrence, but cant seem to find the closed form because the generating function ...
0
votes
0answers
44 views

Discrete dynamical systems

I am given the dynamical system $$x_{n+1}=\frac{1}{2}\bigg(x_n-\frac{1}{x_n}\bigg) \quad \quad \text{ for } n=0,1,2,...$$ I'm then told to substitute $x_n=cot \ y_n$ and find a difference equation ...
-1
votes
1answer
62 views

How to find the polynomial corresponding to positive roots of $f(x)$?

Let $$P_0(x)=1$$ $$P_1(x)=x$$ $$P_n(x)=\frac{(x+\sqrt{x^2-4})^{n+1}-(x-\sqrt{x^2-4})^{n+1}}{2^{n+1}\sqrt{x^2-4}}; n\ge2$$ and $$f(x)=x P_{2n+1}(x)− P_{2}(x).P_{2n-2}(x)$$ It is given that roots ...
2
votes
3answers
41 views

The sequence $a_{n}a_{n+1}=a_{n+2}$

The product of two corresponding terms in a sequence $a_n$ determines the next term. Find the general solution. My approach: $$x^{b+c}=x^bx^c$$ Let $b=F_n$ and $c=F_{n+1}$ then the sum $b+c=F_{n+2}$...
0
votes
1answer
26 views

Solving recurrence equation that appear in biology

I am struggling to solve this recurrence equation, $$a_{n}(1-sa_{n-1}^{2})+sa_{n-1}^2-a_{n-1}=0$$ where the parameter $s\in[0,1]$ and the initial condition $a_{0} > 0$ is close to 1. I have ...
1
vote
1answer
32 views

Limit of $13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}}$

I have the following recurrence: $$13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}},\;a_0=0,\;a_1=1.$$ I have to prove that it is monotone and bounded, and I have to find the limit as $n\to\infty$. It was for an ...
2
votes
0answers
30 views

Need reference for fact about roots of characteristic polynomials of recurrences

Many famous sequences $\{a_n\}$ satisfy recurrence relations. For example, the Fibonacci numbers $\{0,1,1,2,3,5,\ldots\}$ and Lucas numbers $\{2,1,3,4,7,11,\ldots\}$ both satisfy $$ a_n = a_{n-1} + a_{...
-2
votes
1answer
49 views

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$ [closed]

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$: goes to infinity. goes to a finite limit. ...
0
votes
0answers
55 views

Recurrence for the Mertens function generalized to complex numbers.

It is well known that the sum of the Möbius function $\mu(n)$ over divisors is zero unless $n=1$. $$\sum\limits_{d|n} \mu(d) = \delta_{n \, 1}$$ where $$\delta_{n \, 1}$$ is Kronecker delta. Or put ...
5
votes
2answers
191 views

Find the first few Legendre polynomials without using Rodrigues' formula

If a polynomial is given by $$y=\color{red}{a_0\left[1-\frac{l(l+1)}{2!}x^2+\frac{l(l+1)(l-2)(l+3)}{4!}x^4-\cdots\right]}+\color{blue}{a_1\left[x-\frac{(l-1)(l+2)}{3!}x^3+\frac{(l-1)(l+2)(l-3)(l+4)}{5!...
0
votes
1answer
19 views

Is this a valid base case?

I'm trying to prove this for all $n \geq 1$. Using the recursive formula, I ended up with this: $F_{-(n+1)} = F_{-n} - F_{-(n+2)}$. If the formula holds for $n$ and $n+2$, I can eventually turn the ...
3
votes
0answers
57 views

Count number of m-subsets with xor = 0 [closed]

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let $[k]=\{1,2,\...
2
votes
0answers
44 views

Fundamental theorem of arithmetic, prove that these matrices are the same apart from the main diagonal.

I know and I can prove that the fundamental theorem of arithmetic is encoded uniquely by this recurrence written in Mathematica 8: ...
4
votes
2answers
51 views

Simplify the series given by the recurrence relation $na_n=2a_{n-2}$

If you are given a recurrence relation such that: $$na_n=2a_{n-2}\implies a_n= \begin{cases} 0 & \text{odd} \,n \\ \frac{2}{n}a_{n-2} & \text{even} \,n \end{cases}$$ My textbook suggests ...
5
votes
1answer
76 views

Reference request for an identity involving binomial coefficients

The identity is $$\sum_{i\ge 0}(-1)^i \binom{\frac{s^k + s^{-k} - 10}{4}}{i}\binom{\frac{s^k + s^{-k} - 10}{4}+4}{\frac{gs^k + 2g^{-1}s^{-k} - 4}{8}-i}= 0$$ where $k\gt 1$ , $s = 3+2\sqrt{2}$ ...
3
votes
2answers
56 views

Prove that largest root of $Q_k(x)$ is greater than that of $Q_j(x)$ for $k>j$.

Consider the recurrence relation: $P_0=1$ $P_1=x$ $P_n(x)=xP_{n-1}-P_{n-2}$; 1). What is closed form of $P_n$? 2). Let $k,j.\in\{1,2,...,n+1\}$ and $Q_k(x)=xP_{2n+1}-P_{k-1}.P_{2n+1-k}$. Then ...
0
votes
1answer
15 views

Recurrence Relation for QuickSort

Suppose a special recurrence relation for quicksort is: $T(0)=\Theta(1)$ (N>0) $T(N)= T(N-1)+T(0)+\Theta(\sqrt{N}) $ How does this relate to the theta class of: $\Theta(N \sqrt{N})$ ? Can someone ...
3
votes
2answers
64 views

How show that $a_{n}=n$ if $ a_{n+1}+a_{n-1}=\frac{2n}{a_{n}-a_{n-1}}$

define sequence $\{a_{n}\}$ such $a_{1}=1,a_{2}=2$, and such $$ a_{n+1}+a_{n-1}=\dfrac{2n}{a_{n}-a_{n-1}},n\ge 2$$ show that:$$a_{n}=n$$ I want use without induction solve this sequence?
2
votes
2answers
88 views

A square root solving algorithm invented by my friend

Recently, my friend told me a square root algorithm: $$ \left\{ \begin{array}{lll} p_{n+1}&=&p_n+aq_n \\ q_{n+1}&=&p_n+q_n\end{array}\right.$$ Finally, $p_n/q_n$ is near $\sqrt{a}$. ...
3
votes
1answer
54 views

Compute $\sum\limits_{n=1}^{\infty} \frac1{1+x_n}$ if $x_1>0$ and $ x_{n+1} = x_n ^2 + x_n $

Suppose $ x_1\in \Re $ , and let $ x_{n+1} = x_n ^2 + x_n $ for $ n\geq 1 $. Assuming $ x_1 > 0 $, find $ \sum_{n=1}^{\infty} 1/(1+x_n) $. What can you say about the cases where $ x_1 < 0 $? ...
0
votes
1answer
25 views

How to derive the general solution of a recurrence relation?

I know for a recurrence relation $$X(n)=c_1X(n-1)+c_2X(n-2).....+c_kX(n-k)$$ the characteristic equation is $$X^n=c_1X^{n-1}+c_2X^{n-2}+...$$ I know the general solution if all roots are equal is $$...
0
votes
0answers
17 views

recurrence algorithm unfolding with answer, need explanation

SO the question is to prove $O(n\log n)$ hence figure out $f(n)$ correct? why does $n = 2^{2^k}$ what is so special about $2^{2^k}$ can i use another number? this answer is using substitution? I don'...
1
vote
0answers
31 views

Expected sum of picked numbers from set

Let suppose that I have a finite set $X$ of natural numbers. I keep drawing, with reintroduction and uniform probability, from this set until the sum of the extracted numbers, $S$, is bigger or equal ...
3
votes
2answers
32 views

Solve the recurrence relation $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions

Here is what I have so far, or what I know how to do, rather: I am given this equation: $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ So, with the $2a_{n-1}$, I know I can do the following. We change the $...
1
vote
0answers
49 views

Complexity of recurrence equation 6

$B(n)=B(⌈ n/\log_2 n⌉)+\theta(n)$ B(2)=1 Here is my attempt: \begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \...
1
vote
3answers
32 views

Solve the linear recurrence with initial conditions $a_n=a_{n-1}+2^n+1$ and $ a_0 =0$

Let $(a_n)_{n\geq0}$ be the sequence defined by $$a_0=0\qquad\text{and}\qquad\forall n\geq0,\ a_n=a_{n-1}+2^n+1.$$ I know this is a non-homogeneous case and so far as I have gotten the general ...
0
votes
1answer
29 views

To find the Generating function for the given case

$$a_{n} = \frac{4^{3n-5}}{3^{2n+4}}$$ I was just able to reach till $a_{n}$ = ($\frac{64}{9}$) $a_{n-1}$ Don't know how to proceed further
2
votes
1answer
34 views

To calculate generating function

If $a_{n}$ = $\frac {1}{(n-1)(n+1)}$ for $n\ge2$ What are we supposed to do with $a_{0}$ and $a_{1}$? How can I find the generating function without using $a_{0}$ and $a_{1}$?
3
votes
2answers
78 views

How fast does this sequence grow?

I have the following recursive definition of a sequence of numbers: $$a_{n+1}=(a_n)^{(a_{n-1})}$$ And $a_0=a_1=2$. The first few terms are: $$a_2=4$$ $$a_3=16$$ $$a_4=65536$$ $$a_5=1.1579209 \...
5
votes
2answers
78 views

show that $2^k|n\Longleftrightarrow 2^k|a_{n}$

Let sequence $\{a_{n}\}$ such $a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2}$. show that $$2^k|n\Longleftrightarrow 2^k|a_{n}$$ I try to find the $\{a_{n}\}$ closed form $$a_{n}=\dfrac{(1+\sqrt{2})^n-(1-\...
1
vote
4answers
57 views

Recurrence relation involving matrices

I've done part $(i)-(iv) [(i) (C), (ii) (D),(iii) (F), (iv) (E)].$ I would appreciate if someone could show me how to solve this part (v).
2
votes
1answer
31 views

Proving $T(n) = T(n-2) + \log_2 n$ to be $\Omega(n\log_2 n)$

As title, for this recursive function $T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to $O(n\log n)$; however I'm having trouble proving it to be also $\Omega(n\log n)$, i.e. ...