# Tagged Questions

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

47 views

### Prove for all $n\in \mathbb{N}$ ,$n ≥ 1, a(n)$ is odd.

Prove for all $n\in\mathbb{N}\backslash \{0\}$, $a(n)$ is odd. Consider the sequence defined as followed: $a(1)= 1$ $a(2)= 3$,where $n \in \mathbb{N}$ $$a(n)=a(n-2)+2a(n-1), n ≥3$$ Conjecture: ...
5 views

52 views

### Exam Recurrence and Complexity [on hold]

I have an exam coming up in a few days and my prof gave us a couple questions we should know as he will make new questions based on these topics the explanations must be in-depth because it will be a ...
51 views

### Solving $a_n = a_{n-1} + 7n$ for $n\ge1$ and $a_0 = 4$

First, I found the homogeneous solution: $$r^n - r^{n-1} = 0$$ $$\Rightarrow r = 1$$ So the homogeneous solution is of the form: $$c(1)^n = c$$ Then, to find a particular solution, I "guessed" the ...
24 views

### Linear combination of sequence related to Fibonacci

Let $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$. Prove that for all $c,d \in \mathbb{N}$ that $g_n = ca^n + db^n$ satisfies $g_{n+2} = g_{n+1} + g_{n}$ for all $n\in \mathbb{N}$. I'm ...
31 views

36 views

66 views

### Nonlinear recurrence equation $x\to(b/x)+c$ [closed]

I have problem for solving this nonlinear recurrence equation: x_{i}=(b/x_{i-1})+c b,c are constant x_{1}=1
71 views

### Very confused by recurrence relations as a concept

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks: Given the recurrence: $S(1) = 1$, $S(n) = 2S(n − 1) + 3 (for \ n > 1)$ prove ...
789 views

### How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
47 views

### 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 ...
As part of a larger homework task, I'm investigating the following equation, given that $1 \leq s \leq n \in \mathbb{N}$ and $T_n(0) = 0$. $$T_n(s) = \frac{1}{\lfloor \log s \rfloor} [ 1 + \log n + ... 1answer 27 views ### Finding a recurrence for number of paths in a certain tree I have a graph which looks like this: The question is to find a recurrence for a_n - the number of paths of length n that start in vertex A. How do you tackle these kind of problems? There is ... 1answer 23 views ### Proof that linear difference operator, (σ-1)^{k+1} (p) = 0 for all p \epsilon \mathbb{Q}[t], with deg(p) \leq k. I am trying to prove that linear difference operator, (σ-1)^{k+1} (p) = 0 for all p \epsilon \mathbb{Q}[t], with deg(p) \leq k. In this case \sigma(t)=t+1 and \sigma(anything else)=... 0answers 30 views ### Proving J_n(x)N_{n+1}(x)-J_{n+1}(x)N_n(x)=-\dfrac{2}{\pi x}: Part 3 of 3 This is the final part of a calculation that proceeds from this previous question. Here is almost a word for word copy of the textbook question: Use the recursion relations below (for the N_n(x)... 0answers 33 views ### Closed form expression for a two variable recursive relation Let F(m,n) be defined recursively for non-negative integers m and n according to the following rules: F(0,n) = 0 for all n, F(m,n) = F(n,m) for all m and n, and if n\ge m, then F(... 4answers 787 views ### How to find explicit formula for two recursions? I have to find explicit solution for two intertwining recursions$$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$for f(0)=1, f(1)=0, g(0)=0 ,g(1)=1. What ... 2answers 26 views ### Closed form for a certain recurrence relation Can anybody give me a closed form for the (limit of the) recurrence relation a_0 = 0, a_{n+1} = \frac12\cdot\big(1 + a_n^2\big)? And more general: Can anybody give me a closed form for the (limit ... 4answers 314 views ### Limit of x_n^3/n^2 when x_{n+1}=x_n+ 1/\sqrt {x_n} with x_0 \gt 0 Let (x_n)_{n \ge 0} a sequence of real numbers with x_0 \gt 0 and x_{n+1}=x_n+ \frac {1}{\sqrt {x_n}}. Check the existence and find$$L=\lim_{n \rightarrow \infty} \frac {x_n^3} {n^2}$$... 1answer 46 views ### Does the explicit formula for recurrence relation exist Does an explicit formula exist for this recurrence relation? If so, what is it?  f(0) = 1   f(n) = \frac{n}{f(n-1)}  2answers 54 views ### Prove that \Gamma(-k+\frac{1}{2})=\frac{(-1)^k 2^k}{1\cdot 3\cdot 5\cdots(2k-1)}\sqrt{\pi}. I was able to prove that$$ \Gamma\left (k+\frac{1}{2} \right )=\frac{1\cdot 3\cdot 5\cdots(2k-1)}{2^k}\sqrt{\pi}.\tag{$k\geq 1$}$$using the Legendre's duplication formula. But I can't do the same to ... 1answer 24 views ### # of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ... 0answers 40 views ### Solution to a first order linear difference equation The two questions are with respect to the following first order linear difference equation (Y_{t} - Y_{t-1}) = (1-\lambda) (X_{t-1} - Y_{t-1}), for t \geq n Also, note that the process ... 1answer 51 views ### First-Order Linear Difference Equation with Constraint Consider the following first order linear difference equation for y:$$y_{t+1} = \alpha * y_{t} + \beta * x_{t-n+1} ~~\forall t \ge n$$For initial conditions, one could assume that x_{i} ... 3answers 269 views ### How can I find an explicit expression for this recursively defined sequence? We define the sequence (u_n)_{n=1}^\inftyby:$$u_{n+1}=1+\frac{1}{u_n}$$How can I find the limit of this sequence as it goes to infinity? By induction, I can prove that it is bounded above and ... 3answers 61 views ### Finding a closed form for \sum^{n}_{k=1} \frac{k}{(k+1)!}  I'm finding a closed form to \sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1)  (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ... 0answers 21 views ### rearranging a linear first order recurrence Page 26 of Mathematics for Economics and Finance by M. Anthony and N. Biggs states the following equation, y' = ay' + b, and rearranges it as follows (1 - a)y' = b. I do not understand how the ... 0answers 32 views ### Does this family of sequences have the limit \left(\frac{x^{2p}-y^{2p}}{2p(\ln x-\ln y)} \right)^{1/2p} for p \in \mathbb{R}? Define the following family of one parameter sequences:$$a_0=x,~~~b_0=ya_{n+1}=\sqrt{a_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}},~~~b_{n+1}=\sqrt{b_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}}$$I conjecture ... 1answer 35 views ### Simplifying this series of Laguerre polynomials I trying to figure out whether a simpler form of this series exists.$$\sum_{i=0}^{n-2}\frac{L_{i+1}(-x)-L_{i}(-x)}{i+2}\left(\sum_{k=0}^{n-2-i} L_k(x)\right)$$L_n(x) is the nth Laguerre ... 2answers 73 views ### How do I prove the relationship between I_n:=\int_{0}^{\pi}(\sin x)^ndx and I_n=\frac{n-1}{n}I_{n-2} by partial Integration? For all n \in \mathbb{N} : n≥2, I might add.$$I_n:=\int_{0}^{\pi}(\sin x)^ndxI_n=\frac{n-1}{n}I_{n-2}$$I've tried to rewrite \int(\sin x)^ndx to the form \int(\sin x)(\sin x)^{n-1}dx ... 1answer 2k views ### Concrete Mathematics - Towers of Hanoi Recurrence Relation I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ... 1answer 1k views ### Concrete Mathematics - The Josephus Problem I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: J(1) = 1 J(2n) = 2J(n) - 1 J(2n+1) = 2J(n) + 1... 2answers 459 views ### Convergence of sequence:  \sqrt{2} \sqrt{2 - \sqrt{2}} \sqrt{2 - \sqrt{2 - \sqrt{2}}} \sqrt{2 - \sqrt{2 - \sqrt{2-\sqrt{2}}}} \cdots  =? In other words, if we define a sequence$$ \displaystyle a_{n+1} = \sqrt{2-a_n}, \,\,\,a_0 = 0 .$$Then, we need to find$$ \displaystyle \prod_{n=1}^{\infty}{a_n}.  Well, from here I don't seem ...
I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of ...