Questions regarding functions defined recursively, such as the Fibonacci sequence.
2
votes
4answers
69 views
How to solve this recurrence relation?
There's a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair?
I came up with the solution $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$ ...
1
vote
3answers
39 views
Simple Solutions to Homogeneous Recursions
Let $b_n - 2b_{n-2} + b_{n-3} = 0$ be a linear homogeneous recursion. I was able to solve this using a characteristic equation but deriving coefficients became incredibly messy. However, I thought ...
0
votes
1answer
61 views
Given a random sequence give a recurrence defining it.
I heard that there's some hard way to mechanically obtain a recurrence relation for a given sequence. Do you know something about it/where can I find information about it?
2
votes
1answer
71 views
Pascal Triangle Related Problem: Fibonacci Sequence on sides
I have this triangle:
$$\begin{array}{}
&&&&&&&1\\
&&&&&&1&&1\\
&&&&&2&&2&&2\\
...
0
votes
2answers
140 views
Finding Particular Solutions to Non-Homogeneous Recurrence Relations
Could anyone assist me in solving the following recurrence relations?
$a_n = 3a_{n-1} - 2a_{n-2} + 2^n n^2$
$b_n = -nb_{n-1} + n!$
Specifically, I am not sure how to find the particular solutions ...
0
votes
1answer
32 views
Split ${n\over2}\sum_{j\ge 1}2^{-j}(1-2^{-j})^{n-1}$ into oscillating terms.
Exercise 8.57 from Analysis of Algorithms (Sedgewick/Flajolet) asks for solving $p_n=2^{-n}\sum_k{n\choose k}p_k$ up to the oscillating term, for $p_0=0$ and $p_1=1$.
I was able to find a functional ...
6
votes
2answers
41 views
The limit of a recurrence relation (with resistors)
Background to problem (not too important):
My proposed solution:
The infinitely long element,
, however complex, can be represented as a single resistor of resistance $R$.
Remembering the ...
-6
votes
1answer
423 views
How to find a Recurrence Relation from a word problem?
Suppose you have 5 kinds of wooden blocks: red blocks which are 2 inches high, blue
blocks which are 2 inches high, green blocks which are 2 inches high, yellow blocks which are 3 inches high, and ...
3
votes
4answers
135 views
Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$
Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$:
$$
T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)
$$
...
-2
votes
1answer
169 views
Find a closed form for a generating function and recurrence
Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$
for $n \geq 2$ and initial conditions $r_0 = ...
2
votes
3answers
44 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
48 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 ...
0
votes
2answers
30 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
108 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
65 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
61 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
33 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
49 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
46 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 ...
0
votes
3answers
50 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
68 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
35 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
22 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
20 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
72 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
65 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
79 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
0answers
190 views
Question about $f_n=f_{n-1}+\ln f_{n-1}$ with $f_0=2$ [closed]
Let $n,m$ be strictly positive integers.
Let $f_0 = 2$. Let $f_n=f_{n-1}+\ln f_{n-1}$.
Let $h_{n,1}=\sinh^{-1}\left(\dfrac{n}{2}\right)$ and $h_{n,m}=\sinh^{-1}\left(\dfrac{h_{n,m-1}}{2}\right)$.
...
1
vote
1answer
96 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
57 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
74 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 ...
0
votes
0answers
52 views
Determining the Rate of Convergence for Gradient Descent (Steepest Descent) Method
I am not sure how to determine the rate of convergence for this process. Given the recursion x(k+1) = x(k) + af'(x(k)) for a = 1/f''(x) it is apparently the case that the order of convergence is at ...
2
votes
1answer
85 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
149 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
41 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
2answers
41 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 ...
0
votes
1answer
87 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
85 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
22 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
25 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
41 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
0answers
97 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) $$
...
1
vote
1answer
58 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
381 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
69 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) ...
1
vote
2answers
64 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
2answers
134 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
60 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
88 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*}
...
2
votes
1answer
130 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) + ...
