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

learn more… | top users | synonyms (2)

1
vote
1answer
51 views

Stirling number of Second kind generating function

I would like to prove that: $$f_m(x) = \dfrac{x^m}{(1-x)(1-2x)...(1-mx)}$$ Where $$f_m(x) = \sum_{n=0}^{\infty} S(n,m)x^n$$ and $S(n,m)$ is stirling number of 2nd kind Multiplying the recurrence ...
2
votes
1answer
38 views

Approximating logarithmic series

I'm trying to solve the below recurrence $$T(n) = 2 T(n/2) + n/\log n$$ I referenced some online articles they all are approximating $n \sum_{i=0}^{h-1} \frac{1}{\log n - i}$ to $n ...
1
vote
1answer
43 views

Finding recurrence relation 2 - Ternary sequences. [duplicate]

for $n \ge 1$ , Let $f(n)$ be the number of ternary sequences {$0,1,2$} of length n, that the sum of their characters are even, and they have at least one show of $0$. How do i find the recurrence ...
0
votes
2answers
46 views

Number of ternary sequences ${0,1,2}$ of length n without two consecutive even numbers.

(I edited the question and erased my last try, cause my understanding of it, was poor) any help would be appreciated.
0
votes
1answer
92 views

How do i solve the recurrence: $f(n)=F(n-1)+f(n-2)+1$

How do i solve the recurrence: $f(n)=F(n-1)+f(n-2)+1$? My first attempt was to "guess" a private solution to the nonhomogenous which got me : $ f(n)= -1 $ and the corresponding is $F_n$ (fibonacci), ...
6
votes
5answers
259 views

All the ternary n-words with an even sum of digits and a zero.

I'm trying to find a recursive formula for all the ternary (using ${0,1,2}$) sequences of length $n$ which contain at least one zero, and have an even sum of digits. My attempt so far is added below. ...
0
votes
1answer
21 views

two series recurrence relation

Given the recurrence $\begin{cases} F_n = 2F_{n-1}^2 H_{n-1} \\H_n = 2F_{n-1} H_{n-1}^2 \end{cases} \text{ for }n\geq 3$ and $F_2 = 1$, $H_2 = 3$. How can I find an explicit expression ...
0
votes
1answer
23 views

Give a recurrence relations & base cases for the number of $n$ digit decimal strings containing an even number of $0$ digits.

Give a recurrence relations & base cases for the number of $n$ digit decimal strings containing an even number of $0$ digits. My solution is: Let $a_n$ denote the the number of $n$ digit ...
5
votes
3answers
96 views

What are the possible limits of the iteration $x_{n+1}=\sqrt{x_n+3}$, $x_0=0$?

Let $f(x)=\sqrt{x+3}$ for $x\ge -3$. Consider the iteration $$x_{n+1}=f(x_n),x_0=0;n\ge 0$$ The possible limits of the iteration are -1 3 0 $\sqrt{3+\sqrt{3+\sqrt{3+\cdots}}}$ I think only ...
7
votes
0answers
41 views

Bounds (and range) of a nonlinear difference equation

I'm interested in the following set of nonlinear difference equations: $$x_{n+1} = \frac{c + x_n}{x_{n-1}},\; x_1 = x_0 = 1 \qquad \textrm{for } c > 0$$ For $c=1$ the sequence is periodic with ...
0
votes
0answers
112 views

Converting a 1st order non-linear recurrence to a 2nd order

I came across this problem while reading Blelloch's Prefix Sums and Their Applications: Show how the recurrence $x_i = a_i + b_i/x_{i-1}$ where + is numeric addition and / is division, can be ...
0
votes
0answers
17 views

Z transform to difference equation?

For a z transform to fully describe an equation, you need the z transform itself and the ROC. You can convert the z transform to a difference equation easily if it's rational. How can I covert the ...
6
votes
2answers
92 views

Recurrence for expected length of Gaussian vector

Let $g_k \sim N(0, I_{k \times k})$ be a a standard $k$-dimensional Gaussian vector. Denote by $\|g\|$ the $2$-norm of $g$. By explicit integration, it is not hard to see that $$ \mathbb E \|g_k\| = ...
2
votes
5answers
115 views

Solution to the recurrence relation

I came across following recurrence relation: $T(1) = 1, $ $T(2) = 3,$ $T(n) = T(n-1) + (2n-2)$ for $n > 2$. And the solution to this recurrence relation is given as $$T(n)=n^2-n+1$$ However ...
1
vote
2answers
76 views

All the binary n-words without the sequence 011

I'm trying to find a recurrence relation for the binary words of length $n$ that don't contain the sequence $011$, my attempt is as follow: denote $f\left(n\right)$ as the number of such sequences. ...
1
vote
2answers
60 views

Counting Polar Bears

My class is starting to work with generating functions, and I've been working on a problem related to the counting of polar bears. Suppose that there is this bar that polar bears really like to get ...
3
votes
1answer
32 views

Decide if a stack of overhanging blocks is stable

Suppose I have overhand blocks $1,2,3$ up to $n$ units long, one of each kind. They are stacked over the table from smallest to largest so that their left edge alligns. Show if it is stable. ...
9
votes
1answer
66 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
2
votes
2answers
64 views

Is it possible to solve this recurrence relation?

For any real $0<x\leq1$, let $E(x)=1$. For any reals $0<a_1,a_2,\ldots,a_n\leq1$ with $a_1+a_2+\cdots+a_n\leq1$, let $E(a_1,a_2,\ldots,a_n)=1+\displaystyle\sum_{k=1}^n\dfrac{a_k}{1-a_k} ...
1
vote
1answer
30 views

Finding a recurrence relation in combinatorics.

let $ S(n,k)$ be the number of options to divide $[n]$ to $k$ non-empty subsets. find $ S(n,1)$ and $ S(n,2)$. find recurrence relation for $ S(n,k)$. Ok, so my attempt was: $S(n,1)=1$ , because ...
3
votes
3answers
65 views

Solving a recurrence relation.

So I extracted this recurrence relation from a problem that I need to solve: $$ g(n) = 2g(n-1) + \sum_{i=0}^{n-2} g(i) + 1. $$ with $$ g(0) = 1. $$ All I know are two methods of linear homogenous ...
0
votes
0answers
22 views

How can i show why this linear recurrence relation is satisfied? And why it works?

We have a sequence of $n$ numbered parking spaces which are arranged in a line. Type A vehicles require one parking space and Type B vehicles require two parking spaces. Let $H(n)$ denote the ...
0
votes
0answers
16 views

Assessing the stability of a recurrence relation

For a homework assignment I have to consider the recurrence relation $$y(n+1) = h_\beta(y(n)), \quad n \geq 0,$$ where $h_\beta:\Bbb R \to \Bbb R$ is defined by $$h_\beta(x) = ...
0
votes
0answers
14 views

Number of strings of length n consisted of 0,1, 2 such that no two 0s OR 1s are consecutive [duplicate]

I dont know how to deal with this problem as I was used to work with 0 and 1! I get stuck at the beginning. Thanks for ur help in adbance.
1
vote
0answers
33 views

How to solve the recurrence $T(n,m) = T(n/2,m) + T(n,m/2) + nm$ in terms of big O notation?

In every step one of the variables is divided by 2, so I think the depth must be $\log n + \log m$. So the solution is $O(nm(\log n + \log m))$ However for some reason an article I am reading claims ...
1
vote
4answers
154 views

Plugging number back into recurrence relation

I have this problem that I already solved the recurrence for: $$T_{n} = T_{n-1} + 3, T_{0} = 1$$ I worked it out to $T_{n-4} + 4[(n-3)+(n-2)+(n-1)+n]$ (where I stopped because I saw the pattern), ...
0
votes
1answer
22 views

Solving second-order linear homogeneous recurrence relations with constant coefficients $b,c$

I am having problems understanding how to solve second-order linear homogeneous recurrence relations with constant coefficients $b,c$. I have a clear understanding on solving second order linear ...
0
votes
0answers
29 views

Arithmetico-geometric mean and recurrence: prove the two sequences have the same limits [duplicate]

the sequences $(x_n)_{n\geq 1}$ and $(y_n)_{n\geq 1}$ are given by: $$\begin{align} x_1&=a \\ y_1&=b \\ x_{n+1}&= \sqrt{x_ny_n}\\ y_{n+1}&=\frac{x_n+y_n}{2} \end{align}$$ Prove that ...
3
votes
2answers
64 views

Count the number of 10 digit numbers with given condition

PROBLEM: Count the number of 10 digit numbers with digits from $\{1, 2, 3, 4\}$ and no two adjacent digits differing by $1$. I am able to provide a solution using recursion but it is a very ...
1
vote
1answer
36 views

Exponential Generating Function Fun

Given the recurrence relation of $a_n = a_{n-1} + n$, for $n \gt 0$, Where $a_0 = 1$. I know the solution is: $a_n = \frac{1}{2}n^2 + \frac{1}{2}n + 1$. I am not having troubles finding this ...
0
votes
0answers
14 views

Recurrence equation for equivalent (charasteristic) classes in graphs

Is there any Recurrence equation to get the number of equivalent classes in graphs? For example if you have: 2 vertex in a graph there are 2 equivalent classes 3 vertex in a graph there are 4 ...
1
vote
2answers
48 views

Finding the recurrence relation.

So the question has 2 parts to it. Let $f(n)$ be the number of sequences in length n that are built of 0, 1, and 2, so that after zero there's always 1 right after it. Let $g(n)$ be the number of ...
5
votes
2answers
172 views

Is it possible to compute factorials by converting to matrix multiplications?

An $n$-th term of the Fibonacci sequence can be computed by a nice trick by converting the recurrence relation in a matrix form. Then we compute $M^n$ in $O(\log n)$ steps using exponentiation by ...
3
votes
1answer
32 views

How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)
1
vote
1answer
85 views

Ternary strings (combinatorics, recurrence)

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of: a) recurrence relation b) combinatorial expression After that, ...
1
vote
2answers
56 views

Solving $U_{n+1}=(U_{n})^{2} (n+2)$

I need help solving the recurrence relation: $U_{n+1}=(U_{n})^{2} (n+2)$, with $U(1)=2$. I've tried wolfram alpha, but something really horrible came up. The methods I've tried have just failed so I ...
3
votes
0answers
80 views

Permutation and Combinatorics Problem

A function $G$ is defined on a set $S$ with size $k$ : $G(a_1,a_2,a_3,\ldots,a_k)$. $G(a_1,a_2,a_3,\ldots,a_k) = 1$ if and only if a convex polygon can be created by taking these $k$ elements as the ...
2
votes
1answer
44 views

How do you solve this recurrence relation/use it in a sequence to find it's GIF value?

The sequence {$x_k$} is defined by $x_{k+1} = x_k^2 + x_k$ and $x_1=\frac{1}{2}$. Now, if [.] denotes the greatest integer function, then which of the following options is correct: A) $[\frac{1}{x_1 ...
1
vote
1answer
49 views

Finding the reccurence relation from a problem.

let $f(n)$ be the number if ways to lay down tiles in a formation of size 2 x n using tiles of size: $$ \begin{matrix} 1 \\ 1 \\ \end{matrix} $$ and tiles of size: $$ ...
3
votes
0answers
66 views

Solve the Recurrence relation : $a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$

$a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$ I'm ask to get an expression for $a_n$. So i tried to solve with induction: ...
2
votes
3answers
483 views

How to find formula for recursive sequence sum?

I have the following sequence: $$a(1) = 1$$ $$a(n) = a(n-1) + n$$ For example: $$a(1) = 1$$ $$a(2) =3$$ $$a(3) =6$$ $$a(4) =10$$ $$a(5) =15$$ $$a(6) = 21$$ Which approach should I use in order to ...
0
votes
1answer
57 views

Find the recurrence relation

Assume that a must course lasts for $2$ hours while both a technical elective course and a free elective course lasts for $1$ hour. Find the recurrence relation for the number of ways to arrange ...
1
vote
1answer
35 views

Solving recurrence relations of n rabbits on island

Okay so one pair of rabbits is left in an island. After 1 month it produces 2 pairs of rabbits, and 2 months or older they produce 6 every month. I came up with the recurrence relation $ A_{n} = ...
1
vote
2answers
98 views

Solve the recurrence relation : $f(n) = 1 + \frac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$

For naturals $n$, $f(n) = 1 + \dfrac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$. What is $f(n)$? This is not a homework problem. Is there a general method to solve these recurrence relations? I will ...
0
votes
0answers
33 views

Deriving difference equation from a rational system function $H(z)$

If I have the system function $H(z)$ of a linear time-invariant system, how do I derive the difference equation relating its input $x(n)$ and output $y(n)$? The system function is given by $$H(z) = ...
0
votes
1answer
24 views

Can somebody explain the steps in this recurrence back substitution problem?

I'm usually good until the first couple of steps, then once you add more and more things I get lost pretty easily. Can somebody give me a step-by-step analysis of this? I'd really appreciate it. ...
0
votes
1answer
26 views

Recurrence relation for binary strings of length $n$ that doesnt contain $010$ pattern?

I've looked up this question in here and found one whose answer didnt look complete to me or maybe I couldnt figure it out correctly.. I can understand the first part of the answer $a_n = a_{n-1} + ...
0
votes
1answer
58 views

Need to solve this recurrence relation

We are provided with a recurrence relation as follows:- $F(n,k) = F(n,k-1) + F(n-k+1,k)$ $F(n,1) = n $ $F(X,k) = 0$ if $ (X\leq0)$ I need help in solving this for k=1 to 10 only Edit:- I have ...
1
vote
1answer
35 views

Time Complexity recurrence

When we have the recurrence $T(N)=T(N-1)+T(N-2)$, one normally uses $x^N$ and solves for $x$ which gives the golden ratio. But why does one use $x^N$ and not something else, like $\log(N)$ or $N$?
2
votes
2answers
41 views

How to use recurrence to define generating function? How to write generating function as power series?

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to ...