# Tagged Questions

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

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 ...
29 views

### How is this recursion for horizontally convex polyominoes clear according to author?

How is the recursion $a(m,n)$ clear? I don't understand how this is clear.
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!
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)$ ...
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 ...
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$
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 ...
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 ...
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 ...
43 views

### Relation between two sequences or summations

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

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 ...
18 views

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: ...
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 ...
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}$ ...
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 ...
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 ...
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?
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}$. ...
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$? ...
25 views

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-\...
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).
### 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. ...