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

learn more… | top users | synonyms (2)

1
vote
1answer
20 views

How many recurrence relations are possible for a sequence?

How many recurrence relations are possible for a sequence? Example: 5, 11, 29, 83, 245, .... We have 2 recurrence relation: T(n) = 3T(n-1) - 4 T(n) = T(n-1) + 6*3^(n-1) Both give T(n) = 3^n + 2
0
votes
1answer
23 views

Using Difference Equations to Solve Word problems

While I was studying about finite differences I noticed a question in difference equations.Does anyone knows how to solve this using difference equations? WORD PROBLEM Imagine you are to jump from ...
-1
votes
1answer
41 views

need the steps on how to do this recurrence relation question

Given $T_0=0 $ and $T_n=T_{n−1}+n \forall n\in \mathbb N$ use the method of substitution to derive an explicit formula for $T_n$. Prove the validity if your formula.
-2
votes
3answers
37 views

recurrence relation stairs problem

Find a recurrence relation for S(n) the number of ways to climb n stairs if the person climbing can take one stair or two stairs at a time. What are the initial conditions?
0
votes
1answer
28 views

Solution for $T(n) = 2T(\sqrt{n}) + log_2(n)$ [closed]

Solve for: $T(n) = 2T(\sqrt{n}) + log_2(n)$ with no base conditions.
1
vote
0answers
52 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
1
vote
2answers
56 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
0
votes
0answers
32 views

solving T(n) = 4T(n/2) + n^3 + n*(log(n))^2

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n) = 4T\left(\frac n2\right) + n^3 + n\cdot\log^2 n$$ i tried to solve this also with master method... ...
3
votes
2answers
149 views

Solving a 2 independent variables (2nd degree) recurrence relation

Changes to the recurrences and definition are changed! See here: $f(n, 1) = 2n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$. Question: Is it possible ...
5
votes
1answer
48 views

Recursive identity for elliptic lattice constants $\sum_{\lambda\in\Lambda\setminus0} \lambda^{-2k}$

I am stuck on Exercise 3 in these notes. To keep this question self-contained: we have $\displaystyle\Lambda=\langle\omega_1,\omega_2\rangle=\omega_1\Bbb Z+\omega_2\Bbb Z\subset\Bbb C,$ ...
2
votes
1answer
83 views

Prove the summation involving Stirling numbers of the first kind

I have been trying to prove or disprove this for 2 days now, but i don't even know where to begin. $$ 1 = \sum_{m=1}^{n} \sum_{k=1}^{n} \frac{x^{n-m}(-1)^{n-k-m} \left[\matrix ...
1
vote
1answer
19 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
0
votes
0answers
28 views

How to solve recurrence relation $T(n)=2T(n/2)+4^n$ using characteristic equation method?

With change of variables $n = 2^k$ We get $$T(2^k) = 2T(2^{k-1}) + 4^{2^k}$$ which yields $$S(k) = 2S(k-1) + 4^{2^k}$$ I cannot go further. Here: ...
0
votes
1answer
35 views

Solution to recursion equation

Solve the recursive equation $$ T(n) = T(n-1) * T(n-2) $$ with $T(1) = a$, $T(2) = b$ How do I solve this algebraically? I unrolled the recursion and got a solution of $a^{f_n}b^{f_{n+1}}$, ...
0
votes
0answers
42 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
0
votes
1answer
48 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...
6
votes
0answers
99 views

Minimizing beginning terms of a Fibonacci-like sequence

For $ a, b \in \mathbb{Z}^+ $ such that $ a = b $ or $ 2a < b $, let $ f_{a, b} : \mathbb{Z}^+ \to \mathbb{Z}^+ $ be a sequence that satisfies the following three criteria: $$ f(1) = a, \\ f(2) = ...
0
votes
1answer
52 views

How to find explicit formula using backwards iteration

For this problem I tried to solve it by iterating downward so: an = an-1 - n an-1 = 2*(2an-2 - (n-1)) - n = 4an-2 - 3n + 2 an-2 = 2*(4an-3 - 3n + 2) - n = 8an-3 - 7n + 4 an-3 = 2*(8an-4 - 7n + ...
2
votes
1answer
98 views

Finding a more explicit way to express a coefficient in this summation

I am sorry about the vague title, i really don't know how else to ask the question. So i have came up with the following: $$ 1 = \sum_{k=0}^{n} \sum_{v=0}^{n} \frac{x^{n-k+1} T_{n+1,k+1} ...
1
vote
0answers
25 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
1
vote
1answer
36 views

Ways to fill a $4\times N$ box

Given the integer $N$, we need to tell how many ways exist to fill a $4\times N$ board with $1\times 4$ and $4\times 1$ size boxes. Example: for $N=4$ there are $2$ ways.$ $
0
votes
2answers
38 views

Recursive definition proof

I'm having trouble proving the following: $a_0 = a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$. Prove that all the terms $a_n$ are odd integers. It makes sense since an odd number is of the ...
-1
votes
1answer
26 views

How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$. How do I show that: $T(n)=O(n^2)$ Thank you!! (P.S. I hope it's OK to ask it, but I'm looking for the simple ...
0
votes
1answer
23 views

How to solve $T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$

I need to solve this Recursion Relation:$$T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$$ Do you have any idea how? (I try to find another way instead induction). (We should get: $T(n)=\Theta(n\log n)$) ...
0
votes
1answer
30 views

Recurrence relation for the coefficients of the polynomial $p_n(x) = \prod_{i=0}^{n-1}(x-i)$

Let's consider the polynomials $$ p_n(x) = \prod_{i=0}^{n-1}(x-i)=\sum_{i=1}^{n} a_{n,i}x^i$$. for all $n \in \mathbb{N}$. If $n=1$, then $p_1(x) = x$ and $a_{1,1} = 1$. Since I know that: ...
6
votes
2answers
90 views

Count with only certain digits allowed - And feel a fractal

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he ...
0
votes
2answers
57 views

Solving easy inhomogeneous second order recurrence equations

I know the method of solving the characteristic equation to solve homogeneous second order recurrence equations. Now there is added an inhomogeneous term $c$, a constant. I have seen many ...
0
votes
0answers
12 views

Let $g_n^k=p_{n+k}-p_n$, where $p_n$ is the $n$th prime. Does there exist $g_{k+1}^1=2$ such that $g_1^k,g_2^k,\ldots$ is a “Gilbreath sequence?”

Call $(S_i)_{i=1}^{\infty}$ a Gilbreath sequence if $1=\lvert S_2-S_1\rvert=\lvert \lvert S_3-S_2\rvert-\lvert S_2-S_1\rvert\rvert=\cdots$, i.e., if the sequence can be substituted for the primes in ...
1
vote
2answers
56 views

Solving recurrence relation $f(n) = f(\lfloor\sqrt n\rfloor) + 1; f(1) = 1, f(2) = 1$

As the title shows, I need help approaching a solution for recurrence relation: $f(n) = f(\lfloor\sqrt n\rfloor) + 1$ if $n\ge3$ with initial values $f(1) = 1$, $f(2) = 1$ I am particularly ...
0
votes
1answer
23 views

Painting a circular disk

A circular disk is divided into n sectors, each shaped like a piece of pie and all meeting at the centre point of the disk. Each sector is to be painted either red, green or blue in such a way that no ...
1
vote
0answers
35 views

Recurrence relation sequence (Hard)

I was wondering if this sequence was possible using two base cases? The sequence is $\{-1,0,1,3,13\}$ .. Ive came close by doing $(a_{n-1})^2+a_{n-2}+a_n-1$ which works for everything but the $1$. I'm ...
0
votes
1answer
32 views

Probability of a population increasing from size $N$ to size $N + 1$ in a time interval $(t, t + dt)$?

Let $\lambda$ be the birth rate and consider a time interval $(t, t + dt)$. If we have a population of size $N$ the probability of it increasing to size $N + 1$ within the interval $(t, t + dt)$ is ...
0
votes
1answer
26 views

$T(n)=T(n-1)+O(\log n)$ is $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

I have this Recurrence relation: $T(n)=T(n-1)+O(\log n)$ What is the solution? $T(n)=O(n^2)$ or $T(n)=O(n \log n)$ What I did is: I assume that $T(n)\le O(n^2)$ And that's bring me to $O(n^2)$, ...
1
vote
1answer
18 views

Help with nested intervals/sequences

I really do not understand nested intervals. For example, one of my homework problems is: Let $x_0 \in \mathbb{R}$ and $x_{n+1}=\frac{1+x_n}{2}$ for all $n \in \mathbb{N}$. Prove that $\lim_{n \to ...
0
votes
0answers
16 views

Recurrence Relation (sequence)

I'm trying to find the relation of {-1,0,1,3,13} i've came close thinking it was (an-1)^2+(an-2)+an-1 but i cant seem to get all 5 of my elements to match up. Any ideas on a solution would be ...
0
votes
3answers
46 views

How many bit Strings?…

I have trouble figuring out these types of problems. Could someone help me out, with the different ways to answer it? How many bit strings of length six contain three consecutive 1’s? P.S i thought ...
1
vote
3answers
36 views

recursive to explicit sequence

I am trying to find the explicit formula for the following recursion: $$a_{1}=3,\quad a_{n}=3- \frac{1}{a_{n-1}},\quad n \in \mathbb N,n>1$$ I tried in many ways but I cannot find any ...
2
votes
1answer
38 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
5
votes
1answer
83 views

Does the A001921 linear recurrent integer sequence always yield composite numbers?

Let $(a_n)$ be the A001921 sequence $$ a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$ Is it true that $a_n$ is always a composite integer for any $n\geq 2$ ? UPDATE : I now make a ...
1
vote
2answers
76 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
0
votes
1answer
27 views

Finding specific solution for second order nonhomogeneous recurrence equation

$\ x(n+2)−1/2x(n+1)+1/8x(n)=cos(nπ/2)$ Guess a solution -$\ Acos(nπ/2)+Bsin(nπ/2)$ where A and B are constants There were a question about this exact problem yersterday - Need help finding specific ...
0
votes
0answers
22 views

Solving this equation involving a floor

I'm trying to prove that the following recurrence is in $\mathcal{O}(n^4)$: $$f(x) = \left\{ \begin{array}{lr} 10 & ; n=10\\ 3f\Big(\Big\lfloor \frac{2n}{5} \Big\rfloor \Big) ...
1
vote
2answers
42 views

Question about recurrence relation problem.

solve the following recurrence relation, subject to given initial conditions. $a_{n+1} = 6a_n -9,$ $a_0 = 0,$ $a_1 = 3.$ Here is what I have done. $a_{n+1} - 6a_n +9 = 0$ $a_n = r^n$ $r^{n+1} ...
0
votes
2answers
24 views

how many even number faced dice will be their if 99 dices roll for eternity with some condition

Consider a six ­sided dice with number from 1 to 6. Imagine you have a jar with 99 of such dices. You throw all dices on the floor so they all land at different numbers. You look at one dice at a time ...
1
vote
1answer
50 views

Proving a Recurrence Relation by induction

I have the Recurrence Relation: $ T(n)=T(log(n))+O(\sqrt{n}) $, and I'm being asked to prove by induction an upper bound. I'm also allowed for ease of analysis to assume $n=2^m$ for some $m$. So here ...
0
votes
1answer
31 views

Need help finding specific solution for second order nonhomogenous recurrence relation

$x(n+2)-\frac{1}2x(n+1)+\frac{1}8x(n)=\cos(n\pi/2)$ Guess a solution -- $Acos(n\pi/2)+Bsin(n\pi/2)$ where A and B are constants How do I go about this? Any help is appreciated
0
votes
0answers
43 views

How to solve the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$

It seems to me that the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$ has a tight upper bound of: $O(n^{1/2})$, however I am not sure how to prove this. Specifically, I would like to find an ...
3
votes
2answers
35 views

Problem to understand a recurrence relation

In Norris, Markov chains, I found the following: [...] a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ were both non-zero. Let us try a solution of ...
1
vote
0answers
43 views

Difference equation of second order system with zero

I saw from lecture notes that difference equation of a first order system is like this: (1) (2) (3) (4) 1. What happens between (3) and (4)? It looks like inverse Z-transform but according ...
4
votes
3answers
257 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...