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

learn more… | top users | synonyms (2)

2
votes
3answers
144 views

Mathematical induction proof; $g_k=3g_{k-1} - 2g_{k-2}$

Can someone help me with this problem? I'm having a hard time proving this. It's been a long time since I have done mathematical proofs. Suppose that $g_1,\ g_2,\ g_3,\ \ldots$ is a sequence of ...
2
votes
3answers
171 views

Corresponding numerator of the fraction

I am stuck at this question cant think of how to resolve this, sorry I did try to do working but can't think of any right solution. The question is If the denominator is $9900$, then what is the ...
2
votes
4answers
2k views

Finding the limit of a recursive sequence $x_{n+1}=\frac{1}{2}(x_{n}+\frac{M}{x_{n}})$

Define the sequence $\{x_n\}_{n\in\mathbb{N}}$ by $$x_0=\frac{M}{2}, \qquad x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{M}{x_{n}}\right)$$ where $M\in\mathbb{R}$, $M\geq 0$. Find ...
2
votes
2answers
2k views

Characteristic equation of a recurrence relation

Yesterday there was a question here based on solving a recurrence relation and then when I tried to google for methods of solving recurrence relations, I found this, which gave different ways of ...
2
votes
1answer
412 views

Solving recursion with 2 parameters

How do i solve a recursion like this: $c_{i,j} = c_{i,j-1} + c_{i-1,j}$ with $c_{i,0} = c_{0,j} = 1$ After one step it can be written as: $c_{i,j} = c_{i,j-2} + 2c_{i-1,j-1} + c_{i-2,j-1}$ which ...
2
votes
2answers
120 views

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 ...
2
votes
1answer
356 views

About the positive sequence $a_{n+2} = \sqrt{a_{n+1}} + \sqrt{a_n}$

Given the positive sequence $a_{n+2} = \sqrt{a_{n+1}}+ \sqrt{a_n}$, I want to prove these. 1) $|a_{n+2}| > 1 $ for sufficiently large $n \ge N$. 2) Let $b_{n} = |a_{n} - 4|$. Show that $b_{n+2} ...
2
votes
3answers
87 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
2
votes
5answers
129 views

How to give a good guess to the recurrence relation problem [duplicate]

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
2
votes
3answers
58 views

Proof by induction that $f(n) = 1-2^{2^n}$, where $f(0) = 3$ and $f(n) = 2 f(n-1) - (f(n-1))^2$

I am doing a textbook question which state that a function $f:\mathbb{N}\to\mathbb{Z}$ is a recursively defined as shown bellow $f(0) =3$, $f(n) = 2\cdot f(n-1) -(f(n-1))^2 $ if $n\ge1$. Prove that ...
2
votes
3answers
71 views

Why do we set $u_n=r^n$ to solve recurrence relations?

This is something I have never found a convincing answer to; maybe I haven't looked in the right places. When solving a linear difference equation we usually put $u_n=r^n$, solve the resulting ...
2
votes
2answers
53 views

Help with a recurrence relation

I have been battling with the following: $$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$ I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving ...
2
votes
1answer
108 views

How can I make this recurrent equation non-recurrent?

I have a recurrent equation that defines a sequence $a_k$ from a sequence $b_k$: $$a_k = b_k - \sum^\infty_{i=k+1}a_i$$ How can I write this equation without mentioning $a_k$ on the right side?
2
votes
3answers
161 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
2
votes
2answers
377 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
2
votes
2answers
45 views

Maximum of a function from integers to integers

Suppose $f$ is a function form positive integers to positive integers satisfying $f(1)=1$, $f(2n)=f(n)$, and $f(2n+1)=f(2n)+1$ for all positive integers $n$. Job: Find the maximum of $f(n)$ when $n$ ...
2
votes
2answers
82 views

Explicit formula for recurrence

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers. I'm wondering how to get explicit formula for recurrence like ...
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 ...
2
votes
1answer
71 views

recurrence relation

It was some time ago I studied recurrence relations and I came across this one that I cannot solve: $a_{n+3}=-3a_{n+2}+4a_{n}$ with $a_{0}=2$ and $a_{1}=-5$ Ansatz: $a_{n}=r^{0}$ then I get ...
2
votes
2answers
101 views

Find $a_{2012}-3a_{2010}/3 a_{2011}$ where the sequence $a_n$ is determined by roots of a quadratic equation

If $\alpha$ and $\beta$ are the roots of $x^2-9x-3=0$, $a_n=\alpha^n-\beta^n$ and $b_n=\alpha^n+\beta^n$, then find the value of $\dfrac{a_{2012}-3a_{2010}}{3 a_{2011}}$ and ...
2
votes
1answer
101 views

Strange square brackets in recurrence equation

I have the following recurrence given: $$a_{0}=1$$ $$a_{1}=1$$ $$a_{n}=3a_{n-2}+3a_{n-1}$$ Why is that equal to something like this?: $$a_{n}=3a_{n-2}+3a_{n-1}-2[n=1]+[n=0 ]$$ What are those ...
2
votes
2answers
455 views

Nested roots sequence, how to prove it's monotone and bounded?

Let $a\ge1$ and define the sequence $(x_n)$ recursively by: $$x_1 = \sqrt{a}$$ $$x_{n+1}= \sqrt{a+x_n}$$ Here's what I did: Plugging in some values makes it seem as if the sequence is increasing. I ...
2
votes
2answers
168 views

Recurrence relations problem (linear, 2nd order, constant coeff, homogeneous)

I'm currently stonewalled on this problem, in which I have to solve the following recurrence relation and prove my answers satisfy the recurrence. My boundary conditions are $a_0 = 1$ and $a_1 = 9$. ...
2
votes
3answers
338 views

Solving functional equation for generating function

Find the functional equation for the generating function whose coefficients satisfy $$ a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1 $$ This is what I've tried so far: $$ ...
2
votes
3answers
1k views

How do I find the closed form of a recurrence relation?

I'm stuck on how to find closed forms of recurrence relations. My current problem is: An employee joins a company in 1999 with a starting salary of $50,000. Every year this employee receives a raise ...
2
votes
2answers
156 views

Bessel functions of the first kind

How would I show that $$J_1(x)+J_3(x)=\frac 4x J_2(x)$$ Using the series definition of the Bessel Function, which is $$J_p(x)=\sum ^\infty _{n=0} \frac{(-1)^n}{\Gamma(n+1)\Gamma(n+1+p)}\left(\frac ...
2
votes
2answers
998 views

Using Generating Functions to Solve Recursions

I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$. I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask ...
2
votes
1answer
67 views

Recurrence relation help

The function $\psi_k(n)$ satisfies the recurrence relation: $$\sum_{j=0}^k\binom{k}{j}(-1)^j\psi_j(n)\ln(n)^{k-j}=\psi_k(n)$$ Using this, is there a general way I can re-write the function $ ...
2
votes
3answers
702 views

How to solve second degree recurrence relation?

For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$. But how do you solve second degree? For example $$f(n)=\begin{cases} 1,&\text{for }n=1\\ ...
2
votes
1answer
37 views

How to find out the dependence on past terms from a recurence relation

Suppose I know the generating function.Then how do I find out the dependence of of the $n^{\text{th}}$ term on the past $k$ terms from it?? For eg : Suppose I have the fibonaci series . I know its ...
2
votes
1answer
135 views

How can I express such function as known functions or power series?

$$\int_0^x \cfrac{1}{1+\int_0^t \cfrac{1}{2+\int_0^{t_1} \cfrac{1}{3+\int_0^{t_2} \cfrac{1}{\cdots} dt_3} dt_2} dt_1} dt =f(x)$$ $$\int_{0}^{x} \frac{1}{n+h_{n+1}(t)}{d} t=h_n(x)$$ ...
2
votes
5answers
298 views

Solving the recurrence $t(n)=(t(n-1))^2 + 1$

I am trying to solve the following recurrence relation: \begin{align*} t(1) & = 1, \\ t(n) & =(t(n-1))^2 + 1. \end{align*} I need to prove that $t(n)= k^{2^{n}}$ for some constant $k$. What is ...
2
votes
2answers
147 views

What's the recurrence relation to this problem?

A machine can perform $3$ types of operation $A$, $B$ and $C$. The memory is initially $0$. A Program $P$ is a series of these operations. If the machine does $A$, it will add $1$ to the memory's ...
2
votes
2answers
97 views

Is this recurrence $O(n^2)$?

Is this recurrence $O(n^2)$? $$ \begin{cases} T(1) = a\\ T(n+1) = T(n) + \log_2(n), n\geq 1 \\ \end{cases} $$ I try to solve it like this: $T(n+1) = T(n) + \log_2(n), n \geq 1 $ $T(n+1) - ...
2
votes
3answers
2k views

how to work out a closed form of a sequence

Consider the following linear recurrence sequence. $x_1 = 11$, $x_{n+1} = -0.8x_n + 9,\quad n = 1,2,3, \ldots.$ Find a closed form for this sequence.
2
votes
3answers
175 views

Solving $A(x) = 2A(x/2) + x^2$ Using Generating Functions

Suppose I have the recurrence: $$A(x) = 2A(x/2) + x^2$$ with $A(1) = 1$. Is it possible to derive a function using Generating Functions? I know in Generatingfunctionology they shows show to solve ...
2
votes
2answers
143 views

Recurrence relation/inequality, $S(i) \leq d \cdot \log^c (S(i-1))$

During my reaserch I came across the folowwing recursion ineqaulity, I wonder if someone can help me to give a bound about this $S(i) \leq d \cdot \log^c (S(i-1))$ where $s(1) = c_0$ Thanks! ...
2
votes
3answers
231 views

Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$

How can I prove that the solution for the following recursion equation is $\Theta(n)$: $$T(n)= T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$ Edit: $cn$ on one side only. What I need to ...
2
votes
1answer
419 views

How to solve this recurrence relation? (convolution integral)

Following is a recurrence relation written by Robert Israel from Poisson arrivals followed by locking $u_n(t) = \int_0^{t-nT} \lambda \exp(-\lambda y) u_{n-1}(t-y-T)\, dy$. The solution he ...
2
votes
1answer
25 views

Tower of Hanoi variation from Concrete Mathematics - possible arrangements

From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. ...
2
votes
3answers
77 views

Use the generating function to solve a recurrence relation

We have the recurrence relation $\displaystyle a_n = a_{n-1} + 2(n-1)$ for $n \geq 2$, with $a_1 = 2$. Now I have to show that $\displaystyle a_n = n^2 - n +2$, with $n \geq 1$ using the generating ...
2
votes
4answers
158 views

Recurrence relation for right-angled triangles stuck-together

Given the image: and that $x_0 = 1, y_0=0$ and $\text{angles} \space θ_i , i = 1, 2, 3, · · ·$ can be arbitrarily picked. How can I derive a recurrence relationship for $x_{n+1}$ and $x_n$? I ...
2
votes
2answers
46 views

How do I solve the recurrence relation without manually counting?

Given the recurrence relation : $a_{n+1} - a_n = 2n + 3$ , how would I solve this? I have attempted this question, but I did not get the answer given in the answer key. First I found the general ...
2
votes
3answers
54 views

How to solve nonhomgenous recurrence relation?

I'm studying this topic in advance and I'm working on textbook problems. The problem is simple : Solve the following recurrence relation a) $a(n+1)-a(n)=2n+3$, $n$ is greater than or equal to ...
2
votes
2answers
41 views

Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$

I'm trying to solve the following problem: Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$. Is $T(n) \in \mathcal O(2^n)$? I started by finding the time complexity of $T(n) = n\cdot T(n-1) + ...
2
votes
4answers
49 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
2
votes
1answer
76 views

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2.

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2. $a_1=3$ and $a_2=8$ I am having trouble creating the recurrence relation ...
2
votes
2answers
65 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
2
votes
5answers
31 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
2
votes
1answer
33 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...