Articles of recurrence relations

Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$

A question (Problem $7.4$) in my textbook (Mathematical Methods in the Physical Sciences – 3rd Edition by Mary L. Boas P578) asks me to Use $$\int_{x=-1}^{1}(P_L(x)\cdot\text{any polynomial of degree < L})\,\mathrm{d}x=0\tag{A}$$ to prove that $$\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=0\tag{1}$$and gives the hint: $\color{#180}{\fbox{What is the degree of $P_{L−1}(x)$}}$? Also, show that $$\displaystyle\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0\tag{2}$$ Where $P_L(x),P_{L-1}(x)$ represent any general […]

Solving the recurrence relation $T(n)=T(n-1)+cn$

I’ve solved the recurrence relation $T(n)=T(n-1)+cn$ (where T(1)=1), getting $1+c(\frac{n(n+1)}{2}-1)$, but I can’t seem to get the pre-replacement step involving $k$. Here’s what I have: $T(n-1)+cn$ $T(T(n-2)+cn)+cn=T(n-2)+2cn$ $T(T(n-3)+cn)+2cn = T(n-3)+3cn$ $\dots$ $T(n-k)+kcn$ $k=n-1$, so the post-replacement step is $T(1)+(n-1)cn$ This is wrong, however, since $T(3)=1+5c$, whereas $T(1)+(3-1)(3)c=1+6c$ What am I doing wrong here?

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out 🙁 There are T(0) = d and T(1) = e, Thanks in advance.

Recurrence substitution method

I just want to see if I did this right. I need to show that $T(n) = 3T(n/4) + n\log n$ shows that $T(n) = O(n\log n)$ using substitution method in recurrence. $$T(n) = 3c(n/4 \log n/4) + n\log n$$ $$c\log nn – cn + n\log n$$ $$n\log n$$ That does not seem right but […]

derivation of fibonacci log(n) time sequence

I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time. F(2n) = (2*F(n-1) + F(n)) * F(n) which i found on wiki form the fibonacci matrix equation stated there but i stuck in deriving it. I understood the derivation till the (-1)^n = F(n+1)*F(n-1) – F(n)^2 but then how […]

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition – prove recursive formula But the formula from the above link requires a parameter k which is the required number of partitions, but I would like to partition it as far as it could. What I am finding is the partition number of a positive integer n, where […]

recurrence relations for proportional division

I am looking for a solution to the following recurrence relation: $$ D(x,1) = x $$ $$ D(x,n) = \min_{k=1,\ldots,n-1}{D\left({{x(k-a)} \over n},k\right)} \ \ \ \ [n>1] $$ Where $a$ is a constant, $0 \leq a \leq 1$. Also, assume $x \geq 0$. This formula can be interpreted as describing a process of dividing a […]

Question about fixpoints and zero's on the complex plane.

Define property $A$ for an entire function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ $2)$ $f(z)=z$ has exactly one solution $=>z=0$ (follows from $1)$ ) $3)$ $f(z)$ is not a polynomial. Define property $B$ for an entire function $f(z)$ as $1)$ $f(z)=f_1(z)$ with property $A$. $2)$ $f_i(z)= ln(f_{i-1}(z)/z)$ for every positive integer […]

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 be able to prove it…

Period of a sequence defined by its preceding term

A sequence $x_n$ is defined such that $$x_{n+1}= \frac{\sqrt3 x_n -1}{x_n + \sqrt3}, n\ge1, x_0\neq-\sqrt3 $$ We now have to find the period of this sequence. By substituting values for $x_0$ I found out the period to be $6$. Also I proved this by finding all $x_{n+k}, 1\le k \le 6$ in terms of $x_n$ […]