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

learn more… | top users | synonyms (2)

2
votes
3answers
84 views

Divide et impera recurrence, why induction does not work?

$$ T(n) = T\left(\frac n2\right) + 2^n $$ where $n \ge 1$ and $T(1) = 1$. If I understand the substitution method and the induction, I can guess that $T(n) = O(2^n)$. I must prove that $T(n) = ...
2
votes
0answers
76 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
1
vote
1answer
32 views

Inhomogeneous recurrence relation: $x(n) = 2x(n-1)+(n\bmod 2)$

How can I solve a recurrence relation given as $$x(n)=\begin{cases} 2 x(n-1)+1 &n=\text{odd}\\2 x(n-1) & n=\text{even}\end{cases}$$ I know how to solve them individually,$x(n)=a(2^n)$,where ...
0
votes
2answers
110 views

Sequence generated by polynomial expression

For each, find the polynomial expression that gives $a_n$ 1) 1, 6, 17, 34, 57, 86, 121, 162, 209, 262... 2) 4, 4, 10, 28, 64, 24, 214, 340, ... My attempt of 1) is $3x^2+2x+1$ and 2) is $2x^2+x+4$ ...
-1
votes
2answers
132 views

What the recurrence relation for this problem?

For a positive integer $n$, let $a(n)$ denote the number of ways to write $n$ as an ordered sum of integers where each summand is at least $2$. For example, $6$ can be written $6, 4 + 2, 3 + 3, 2 + ...
-2
votes
1answer
144 views

What is the recurrence relation in this problem?

Suppose that you have a large supply of red, white, green, and blue poker chips. You want to make a vertical stack of $n$ chips in such a way that the stack does not contain any consecutive blue ...
0
votes
1answer
243 views

Explicit formula for $a_n$, reccurence relations

For the following, solve each of the following recurrence relations by giving explicit formula for $a_n$ and calculate $a_9$. $a_n = 10 a_{n-1}, a_0 = 3; $ $a_n = -a_{n-1}, a_0 = 5;$ $a_n = 3 a_{n-1} ...
0
votes
2answers
52 views

Recursive polynomial relation

So we have the following: $1^4 + 2^4 + 3^4 + ... + n^4$ How do you find a polynomial formula for this recursive relation? My attempt is to set it up as following: $(n+1)(n^3+1)$ but it does not look ...
0
votes
2answers
214 views

Recurrence relation for n-cube

For a natural number n, the n-cube is a figure created by the following recipe. The 0-cube is simply a point. For n>0, we construct an n-cube by taking two disjoint copies of an (n-1)-cube and then ...
1
vote
1answer
101 views

Stuck finding a recursive recurrence relation.

I am analyzing the following algorithm: QUANT(n): if n == 0 or n == 1: return 1 else return (n-1)*QUANT(n-1) + n I need to find the recurrence relation of ...
2
votes
2answers
147 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 ...
0
votes
3answers
87 views

Recursive/Fibonacci Induction [duplicate]

1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction: $$ F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}} $$ Clear ...
1
vote
2answers
99 views

Solving Another Recursion Using Generating Functions

I am trying to find a closed form for $$ Y(n) = Y(n-1) -2Y(n-2) + 4^{n-2} \text{ with initial conditions } Y(0) = 2,Y(1) = 1 $$ using generating functions. However, I am still not entirely ...
0
votes
3answers
87 views

Recursion Induction

Let $c_0 =3$ and for n>0, let $c_n = c_{n-1} +n.$ What is the first five terms of the sequence? Prove that $$c_n = \frac{n^2+n+6}{2}$$ Need to prove this by induction. Not a homework but I'm trying to ...
0
votes
1answer
30 views

Recurrence relation for number of different square subboards

Find a recurrence relation for the number of different square subboards of any size that can be drawn on an $n\times n$ chessboard. I worked this out up to $n= 4$. For $n=1$, there's $1$, $n=2$ ...
0
votes
1answer
34 views

Zero coefficient of associated homogeneous recurrence relation

When solving a non homogeneous recurrence relation, is it possible for a coefficient in the associated homogeneous equation to be zero? Meaning the solution might consist solely of the particular ...
1
vote
1answer
172 views

Recurrence relation for a sequence

Find a recurrence for the number of words of length n in the alphabet {1,2,...,k} with no 11. $n\in \mathbb{P}$ with $k \geq2$. Please help me.....
2
votes
3answers
90 views

Finding a general solution of $A_n$

Find the general solution to $ A_{n+1} + 4A_n = n $ I am unsure how to even start the question :S
2
votes
3answers
108 views

Please help solve the following recurrences

Please help with solving the recurrences to get closed form formulas for $a_n$, $b_n$ and $c_n$. Be sure to clearly label the characteristic equation, the roots of the characteristic equation, the ...
1
vote
1answer
129 views

Alternative solutions to $n^2+n = k^2+k + 2kn$

Consider this equation: $n^2+n = k^2+k + 2kn$ I want to find the set of non-negative integer n,k that satisfies the equation. I tried to write $n$ as $k$ by solving the equation with $n$ as root ...
0
votes
1answer
716 views

Rate of Convergence for Gradient Descent (Example)

I am trying to determine the rate of convergence for $f(x,y) = 5x^2 + 5y^2 − xy − 11x + 11y$. Would anyone be able to provide guidance as to how I might go about doing this? Should I select my own ...
2
votes
2answers
934 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
1k views

Showing that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$

How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$? What is the resulting equation I get after the substitution? $$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$ ...
0
votes
2answers
405 views

Finding a solution to the recurrence relation $T(n) = T(n-1) + T(n/2) + n$

I have the following recurrence relation $$T(n) = T(n-1) + T(n/2) + n .$$ I know that I cannot use Master's theorem here and by intuition I can see the relation will be of order $O(n^2)$. But how to ...
1
vote
1answer
70 views

recursion relation for sequence of random variables

Let $\dots, \xi(-1),\xi(0),\xi(1),\dots$ be a sequence of i.i.d. random variables on $\mathbb Z$ with $\mathbb E[\xi(n)]=0, \mathbb E[\xi(n)^2]=1$. The process $(X(n))_{n\in \mathbb Z}$ is ...
1
vote
1answer
43 views

Finding equilibrium with two dependent variables

I was thinking while in the shower. What if I wanted to set two hands of the clock so that the long hand is at a golden angle to the short hand. I thought, set the short hand (hour hand) at 12, and ...
1
vote
2answers
311 views

Recurrence relation for the number of ways to arrange $3$ different types of flags

Find a recurrence relation for the number of ways to arrange red flags ($1$ ft. tall), yellow flags (1 ft. tall), and green flags ($2$ ft. tall) on an $n$ foot tall pole s.t. there may not be ...
1
vote
0answers
52 views

Finding the linear representation of an ARMA process

I have the following $ARMA(2,2)$ process: $X_t + 0.9X_{t-1} = Z_t + 1.3Z_{t-1}$ I'd like to write it in the form: $X_t = \sum\limits_{i=0}^\infty\psi_iZ_{t-i}$ I just want to compute the first few ...
0
votes
1answer
359 views

Solving a recurrence relation using Z transform

I'm trying to solve the following recurrence using Z transforms: For $n\in \mathbb{N}^{*}$ $T(n)=1\ for\ n< 4$ $T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq ...
9
votes
2answers
99 views

Proving that $a_n$ is an integer for every $n$

For every $k\ge1$ integer number if we define the sequence : $a_1,a_2,a_3,...,$ in the form of :$$a_1=2$$ $$a_{n+1}=ka_n+\sqrt{(k^2-1)(a^2_n-4)}$$ For every $n=1,2,3,....$ how to prove that $a_n$ is ...
0
votes
0answers
29 views

Is this equation on the right form?

Lets assume there is a list $l$, where its items are denoted as $[a_0,...,a_n]$ and where we only consider the first and last third without the elements in b/n and while doing it recursively until we ...
1
vote
0answers
91 views

genealogy pedigree chart

What is the simple expansion of a (simple) genealogy pedigree chart, where each person (only) has 2 parents? What is that called? Is it an arithmetic progression, or a geometric progression? You start ...
0
votes
2answers
56 views

How to solve this inhomogeneous recurrence difference equation?

$a_n=1+p a_{n-1+k} + (1-p) a_{n-1}$, $a_0=0$ Given that $0<p<1$, $n,k$ are positive integers, and $a_n<\infty$ If I am only interested in real value solutions, how to solve it? If there is ...
0
votes
1answer
200 views

Time-delay differential-difference equation

Is it possible that the system $$ \begin{cases} 2\dot{q}(t) + \dot{q}(t-1) + \dot{q}(t+1) = k & \text{if} \hspace{5mm} 0 \leqslant t \leqslant 2 \\ \dot{q}(t) + \dot{q}(t-1) = c & \text{if} ...
1
vote
0answers
315 views

A recurrence relation for Stirling numbers (2nd kind)

It is well-known that the Stirling numbers of the second kind satisfy the following (vertical) recurrence relation: $$\sum\limits_{r=k}^n \binom{n}{r}S\left( r,k\right) =S\left( n+1,k+1\right) $$ ...
2
votes
0answers
123 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
4
votes
1answer
110 views

How prove this summation

prove that: $$\dfrac{n}{n+1}+\dfrac{2n(n-1)}{(n+1)(n+2)}+\dfrac{3n(n-1)(n-2)}{(n+1)(n+2)(n+3)}+\cdots=\dfrac{n}{2}$$ I think can prove by the probability my idea: ...
1
vote
1answer
78 views

Recurrence Equation with Polynomial Coefficients

As inspired by this question on the problem site Brilliant, Let $F_n(a,b,c)=a(b-c)^n+b(c-a)^n+c(a-b)^n$ Is it possible to obtain $F_n$ in terms of $F_3, F_2$? My attempt at a solution is as ...
1
vote
3answers
2k views

Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s

Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$'s or $2$'s. The solution is $$ a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1 $$ ...
2
votes
2answers
96 views

Twice a triangle is triangle

The question is to prove that there are infinitely many triangular numbers $T_n$ where $2 \times T_n$ is also a triangular number, and give the first few as an example. My attempt: $$2 \cdot {x(x+1) ...
0
votes
1answer
86 views

Solution to system of difference equations with repeated unit roots

Can anyone provide the forms of the solutions for the homogeneous part and particular solutions for a non-homogeneous system of two linear autonomous difference equations ...
1
vote
2answers
218 views

Difference between two methods of induction for proving the correctness of recurrence equation solution

Suppose you have the recurrence equation $T(0) = 0$ $T(n) = 2T(n-1) + 1, n > 0$ The closed form of this equation appears to be $T(n) = 2^n - 1$ To prove this is correct using induction, we have ...
0
votes
3answers
610 views

non homogeneous recurrence relation

I am trying to solve the non-homogeneous linear recurrence relation: $$f(n) = 6f(n-1) - 5,\quad f(0) = 2.$$ How do I go about doing it? This is so different from solving a homogeneous recurrence ...
1
vote
3answers
69 views

recurrence relation expanding $ij$

I need to solve this: $\displaystyle\sum\limits_{i=1}^n$$\displaystyle\sum\limits_{j=1}^n $$\displaystyle\sum\limits_{k=1}^{i\cdot j} 1$ How do I expand the $i\cdot j$ part? Am I right to do it this ...
1
vote
3answers
1k views

Solving recursion with generating function

I am trying to solve a recursion with generating function, but somehow I ended up with mess..... $$y_n=y_{n-1}-2y_{n-2}+4^{n-2}, y_0=2,y_1=1 $$ \begin{eqnarray*} ...
1
vote
1answer
362 views

$T(n) = T(n/2) + T(2n/3) + T(3n/4) + n$ Solve for n

How do I unravel this recurrence relation? $$T(n) = T(n/2) + T(2n/3) + T(3n/4) + n$$ Here's what I've got so far: $$= T(n/4) + t(n/3) + T(3n/8) + T(n/3) + T(4n/9) + T(n/2) + T(3n/8) + T(n/2) + ...
0
votes
1answer
64 views

Derrangments of an -set, Combinatorial proofs, and EGFs

Let $D_n$ be the number of derrangements of an n-set. $D_o=1$. Give a combinatorial proof that $D_n = (n-1)(D_{n-1}+D_{n-2})$ for $n \geq 2$ and find an EGF of {$D_n$}$_{n \geq 0}$.
0
votes
1answer
58 views

Help with difference equations?

I'm reading a book on time series and in the book there is a chapter on difference equations and one part has got the following derivations which is unclear to me: Now suppose that the sequence ...
3
votes
3answers
106 views

Find $ \lim_{n \to \infty } z_n $ if $z_{n+1} = \frac{1}{2} \left( z_n + \frac{1}{z_n} \right) $

How do I approach the problem? Q: Let $ \displaystyle z_{n+1} = \frac{1}{2} \left( z_n + \frac{1}{z_n} \right)$ where $ n = 0, 1, 2, \ldots $ and $\frac{-\pi}{2} < \arg (z_0) < ...
0
votes
2answers
99 views

Second order difference equation with initial conditions

I have been given this difference equation and asked to solve it: $$y_{n+2} + 2y_{n+1} -3y_{n} = 5 \cdot 2^n + 12$$ where $y_{0} = 7$ and $y_{1} = -9$ I know it sounds weird but we have never ...