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

learn more… | top users | synonyms (2)

0
votes
3answers
49 views

Proving a closed-form recurrence by induction

Find the closed form for the following, then prove by strong induction: $$T(n) = \begin{cases} 1\quad &\text{ if } n = 0 \\ 11\quad &\text{ if } n = 1 \\ T(n-1) + 12T(n-2) & \text{ ...
0
votes
1answer
208 views

Find a recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s.

I've been stuck on this one for a little bit now. I've looked at the other similar questions on here, but I don't understand the general process for going about forming a recurrence relation from ...
2
votes
2answers
79 views

Recurrence forlmula for number of permutation.

The problem: Find the recurrence formula for number of permutations if a cube of any such permutation is identity permutation. Solving: We have to count a number of permutations kind of $\pi$, if ...
1
vote
1answer
25 views

How to state a recurrence equation

I'm working on my homework and I saw this problem: A divide and conquer algorithm $X$ divides any given problem instance into exactly two smaller problem instances and solve them recursively. ...
0
votes
1answer
74 views

Finding a closed form of recursive formula $T(n)=4T(n-1) - 4T(n-2)$

Find the closed form for the following: $$T(n) = \begin{cases} 1\quad &\text{ if } n = 0 \\ 4\quad &\text{ if } n = 1 \\ 4T(n-1) - 4T(n-2) & \text{ if } n > 1 \end{cases}$$ ...
0
votes
0answers
41 views

Prove that $p_nq_{n-1}$ - $p_{n-1}q_n=(-1)^{n-1}$ for $p_{-2}=0$ $p_{-1}=1$ $q_{-2}=1$ $q_{-1}=0$

Let $p_n$/$q_n$ for $n=0,1,2,..$ be the convergents of $a∈ R$ $p_{-2}=0$ $p_{-1}=1$ $q_{-2}=1$ $q_{-1}=0$ $p_n= a_np_{n-1}+p_{n-2}$ $q_n= a_nq_{n-1}+q_{n-2}$ I need to prove that $p_nq_{n-1} - ...
0
votes
2answers
19 views

Running time recurrence relation, solving using induction

I am having a hard time figuring out how to solve such problems, here is the one I am trying to solve: T(n) = 1, if n = 1 T(n) = T(n/6) + 2T(n/3) + O(n), if n > 1 I need to show that T(n) is O(n) ...
0
votes
1answer
26 views

Recurrence relationship with 2 sided boundary conditions (not at 0 and 1, but at 0 and $N$)

I have a seemingly straightforward homogeneous second degree recurrence relationship. $$Z(a+2) = 3 Z(a+1) - 2 Z(a) $$ If given boundary condition of $a$ at 0 and 1, I could solve it using standard ...
0
votes
0answers
18 views

m linearly independent solutions for the recurrence relation of an LFSR, Why?

This article claims that there are $m$ linearly independent solutions to the recurring relation of an LFSR, I've noticed that this is true for both of the following recursions: $$b_{i+m} = ...
4
votes
2answers
67 views

Recurrence relationship

How do you solve the following recurrence relationship? $$x_{n} = \frac{x_{n-1}}{1 + x_{n-1}}$$ where $$ x(0) = 1 $$ I know the answer is $$ x_n = \frac{1}{n+1}$$ I solved it by induction. But I ...
1
vote
0answers
27 views

Recurrence relation for this exponentiation algorithm

I am trying to come up with a recurrence relation for the number of multiplications needed for this algorithm: ...
0
votes
0answers
30 views

Find a relation between $v_{n}$ and $v_{n-1}$

Let us consider the sequence $v_{n}$ defined by: $$v_{n}=∑_{i=3}^{n}d_{i}∏_{j=i+1}^{n}a_{j}$$ where $d_{i}$ and $a_{j}$ are two real sequences. My question is: Find a relation between $v_{n}$ and ...
1
vote
0answers
33 views

Upper bound on a sequence after a finite number of steps

i need to find an upper bound (as tightest as possible) of the following recurrence for $\mu^{(j)}$ $$ \left\{ \begin{array}{l} t^{(j-1)} = 2 \mu^{(j-1)} - \nu & j \geq 1\\ \mu^{(j)} = ...
0
votes
0answers
46 views

How to solve $T(n) = 2T ( \frac{n}{2} +\sqrt{n})+ T (\frac{n}{2} ) + 1$

I want to know how to solve the recurrence $T(n) = 2T ( \frac{n}{2} +\sqrt{n})+ T (\frac{n}{2} ) + 1$ and other similar recurrences when they contain $\sqrt{n}$ or when the argument of $T$ contains ...
0
votes
1answer
61 views

How to solve these recurrence relations by using generating function [closed]

First of all, I want to make an apology for my English for I'm not an English native speaker. I'm reading Discrete Mathematics and its Applications recent days, and I am stumped by these three ...
0
votes
3answers
20 views

How do I solve this recurrence relation with the given condition?

Equation: $a_n = a_{n-1}-n$ for the given condition: $a_0 = 4$ So that means I know that $a_1 = 3$, $a_2 = 1$, $a_3 = -2$, $a_4 = -6$, and $a_5 = -11$. I've tried for over 1.5 hours now trying to ...
0
votes
0answers
19 views

Poblation Recurrence system model

I have a poblation model system given by: $ x(n+1) = 0.6 x(n) + 0.5 y(n) $ $ y(n+1) = -0.16 x(n) + 1.2 y(n) $ With $ 2 x(0) < 5 y(0) $ How can i solve that system? I m trying with Casorati ...
0
votes
0answers
39 views

How to solve three recurrences dependent on each other?

Given $a$,$b$,$s$ and $y$. Let $U_0=s$, $V_0=0$ and $W_0=s$, and $U_{n+1}={s b ((1-2 y) V_{n}+2 y W_{n})}/\sqrt{(1-y) (U_{n}^2 a^2+V_{n}^2 b^2)+y W_{n}^2 b^2}$ $V_{n+1}=-s a U_{n} ...
0
votes
1answer
73 views

solving recurrence relations to solve a and b

I am asked A department store offers a budget of account to its customers. Each month interest is charged on any outstanding debt, while a fixed sum has to be repaid at the end of each month. ...
0
votes
1answer
55 views

How to obtain closed form of this recurrence relation?

I have to solve a the following recurrence through iteration. I also show the steps. The issues is I have no idea how to get to the closed form! I can tell there's a pattern, but I don't know how to ...
3
votes
2answers
93 views

How to solve recurrence $T(n) = nT(n - 1) + 1$

Assume $T(n) = \Theta(1)$ for $n \leq 1$. Using iterative substitution. So far I have: \begin{align*} &T(n) = nT(n - 1) + 1\\ &= n((n - 1)T(n - 2) + 1) + 1\\ &= n(n - 1)T(n - 2) + n + 1 ...
-1
votes
2answers
96 views

Use generating functions to solve $a_n = 6a_{n-1} - 8a_{n-2} + 3 $ and… [closed]

Use generating functions to solve: $$a_n = 6 a_{n - 1} - 8 a_{n - 2} + 3$$ With initial condition: $a_0 = 1$ and $a_1 = 0$ $$a_n = 3 a_{n - 1} + 4 a_{n - 2}$$ With initial conditions: $a_0 = 1$ ...
-2
votes
4answers
50 views

Solve the difference equation $x_n-4x_{n-1}+3x_{n-2}=0$, $x_0 = 2$, $x_1 = 5$ [duplicate]

Solve the following difference equation to the specific $x$ values $x_0 = 2$ $x_1 = 5$ $x_n-4x_{n-1}+3x_{n-2}=0$ I need some help and guidance to get this problem started and to ...
1
vote
0answers
40 views

Square root digit recurrence algorithm

I'm reading a book which expose how to compute a square root using the digit recurrence algorithm. Following the book basically it expose a simple case with each step necessary to compute such square ...
0
votes
1answer
25 views

Block diagonal matrix and difference equation

Compute $A^j~\text{for} ~~j=1,2,....,n.$ For the block diagonal matrix $A=\begin{bmatrix} J_2(1)& \\ &J_3(0) \end{bmatrix}$, And show that the difference equation $x_{j+1}=Ax_{j}$ has ...
0
votes
0answers
30 views

solving recursively

The functions f : N → N and g : N^2 → N are recursively defined as follows: f(0) =1, f(1) =2, f(n) = g(f(n − 2),f(n − 1)) if n ≥ 2, g(m,0) =2m if m ≥ 0, g(m,n) =g(m,n − 1) + 1 ...
0
votes
2answers
49 views

First Order Non-Homogeneous Linear Recurrence for Summation

I've been studying Linear Recurrences in the non-homogeneous case, but have gotten stuck with the following problem: Find a closed form for $s_n=\sum_{i=1}^n i$. I know the answer is $n(n+1)/2$ by ...
1
vote
1answer
48 views

The kth derivative of $f(x)=\log^2 x$ by induction, and the recurrence $a_k=(k-1) a_{k-1}+(k-2)!$

When I was working in my next post I've found the problem to compute the kth derivative of $f(x)=\log^2 x$, for $x>0$, Fact. If $f(x)=\log^2 x$, for $x>0$, then the kth derivative, $k\geq ...
1
vote
2answers
63 views

Help with solving recurrence relations using iterative substitution

I need help solving these two recurrences with iterative substitution. I've looked at examples, and tried to follow them, but I just don't understand the whole plugging the recurrence into itself. I ...
0
votes
1answer
36 views

Solve recurrence $a(n+1)= \frac{a(n)}{a(n)+2}$ with $a(0)=1$

Solving recurrence $a(n+1)= \cfrac{a(n)}{a(n)+2}$ with $a(0)=1$ Do I have to make a replace? Can someone help with initial steps? Thanks.
0
votes
2answers
41 views

Finding a recurrence

I am trying to figure out a recurrence for these numbers: $f(1)=0$ $f(4)=16$ $f(16)=128$ $f(64)=768$ The base case is $f(1)=0$ the numbers inputed into f must be powers of 4. I am not sure what ...
1
vote
0answers
46 views

Solving quadratic recurrence relation

I'm seeking a solution (if one is known to exist) to the following recurrence relation: $x_{t+1}^2 = ax_t+bx_t^2$. where $a\in(0,1)$, $b\in(0,1)$. I know $x_0\in(1,3)$, but its value varies ...
-1
votes
1answer
43 views

Is it possible to find a closed form for this recursive sequence?

Is it possible to find a closed form for the sequence defined by $$\begin{align*} a_0&=3\\ na_n&=(n-1)a_{n-1}+1\quad\text{for }n\ge 1\;. \end{align*}$$
1
vote
2answers
64 views

Solve the recurrence relation $a_n = 4a_{n-1} - 3a_{n-2} + 2^n $

Solve the recurrence relation $$a_n = 4a_{n-1} - 3a_{n-2} + 2^n $$ With initial conditions: $a_1 = 1$ $a_2 = 11$ I have done similar recurrence relation problems to this, but ...
0
votes
2answers
32 views

long term recurrence relations and how to recorrect the deficit

I have the following question: In a sales drive a building society is trying to gain new customers. In any 6 month period it estimates that it loses 1.5% of its customers to competitors and ...
3
votes
0answers
105 views

Asymptotic solutions of a sparsely perturbed recurrence relation

Recurrence relation I am trying to find approximate solutions $T(n)$ of the recurrence relation $$ p\ T(n-1) - \left[p+q+\overline{S} + \varepsilon \tilde{S}(n)\right]T(n) + q\ T(n+1) = 0,\\ ...
0
votes
0answers
59 views

Join 2n points in pairs on the circumference of a circle using n non-intersecting chords

Show that if 2n points are marked on the circumference of a circle and if an is the number of ways of joining them in pairs by n non-intersecting chords then an = Cn. -Not sure how to approach this ...
1
vote
3answers
34 views

Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n$ with $a_1=1, a_2=11$

Solve the recurrence relation: $$a_n=4a_{n-1}-3a_{n-2}+2^n$$ With initial conditions: $$a_1=1, a_2=11$$ I know that this is a non-homogeneous recurrence relation meaning that the first step is to ...
0
votes
2answers
36 views

Solve the recurrence relation $a_n={1\over2}a_{n-1}+1$, $a_1=1$

Solve the recurrence relation: $$a_n=1/2a_{n-1}+1$$ With initial conditions: $$a_1=1$$ So far I have: $$Assume...a_n = r^n$$ $$r^n = {1\over2}r^{n-1} + 1$$ $$r={1\over2}+1$$ I have never had to solve ...
0
votes
2answers
107 views

Given the permutation recurrence relation find $a_n$

In bell ringing, successive permutations of n bells are played one after the other. Following one permutation π, the next permutation must be obtained from π by moving the position of each bell by at ...
0
votes
1answer
28 views

Recurrence Relation Question with a sequence

I have stumbled upon a sequence (0,1,4,15,64...) as the solution to a computer science problem I have been studying. The sequence is known and is given by a(n) = n(a(n-1) + 1), a(0) = 0. My question ...
2
votes
0answers
85 views

Solving recursions by calculating determinant of an infinite matrix

In this reference (pg. 4) and few others a specific parameter in a recursion formula is solved by setting the determinant of an infinite matrix to $0$. In this precise case we have $c_{n-1} - D_n c_n ...
0
votes
1answer
48 views

Master theorem for $T(n) = 9T(\frac{n}{3}) +4n^6$

based on master theorem, I arrived at $$n^{2} ,f(n)=4n^6$$. So is the answer $$\theta(4n^6)$$ or is it just $$\theta(n^6)$$. And also, can this be solved with substitution method?
0
votes
1answer
46 views

How to find this recurrence relation,

The problem statement is: Consider the following two infinite sequences: 1,2,4,... and 1,3,9,... Given that the sequences satisfy the same linear three-term recurrence relation, find that ...
1
vote
1answer
19 views

Why does the polynomial recurrence of $P(n)$ of degree $k$ requires a degree $k+1$ polynomial for its closed form?

Suppose we have a recurrence defined in the following way: $$a_n=a_{n-1}+n^2-3n$$ $$a_0 = 1$$ which produces the following sequence: $$1, -1, -3, -3, 1, ...$$ In order to find the polynomial closed ...
7
votes
1answer
42 views

prove the sequence is increasing

Im asked to show the sequence $a_{n+1}=\sqrt{3+2a_{n}}$ where $a_{1}=0, a_{2}=1$ is increasing and bounded and therefore convergent. I don't even know how to start the proof. Im sure it increases ...
0
votes
1answer
40 views

Solve the recurrence relation $T(n) = nT^2(n/2)$

Solve the recurrence relation $T(n) = nT^2(n/2)$ with initial condition $T(1) = 6$. So far I believe that I should let $n = 2k$ and then make the substitution for $ak = \log T(2k)$. From here I am ...
0
votes
3answers
72 views

Explicit formula for a recurrance relationship $A_n = A_{n-1} + 2n + 1$

$$a_n = a_{n-1} + 2n + 1 $$ $$ a_0 = 1 $$ $$ a_1 = 4 $$ $$ a_2 = 9 $$ I know the basics of how to use characteristic polynomials, but I'm not sure how the $2n$ would be represented in the ...
3
votes
1answer
39 views

Solution to this recurrence?

Is there exists a solution to this recurrence. $$F(N,1) = N, N≥1$$ $$F(N,K) = \frac {1}{\lfloor\frac 1{F(N-1,K-1)} -\frac 1{F(N,K-1)}\rfloor} \;\;\;\;2≤K≤N$$ I tried to simplify the equation but i ...
0
votes
1answer
26 views

Inverting functions containing ceiling

I have a recurrence relation for a countably infinite sequence that contains the integers divisible by 5 but not by 7. The relation I came up with is: $5((n-1) + \lceil \frac{n}{6} \rceil)$ The ...