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

learn more… | top users | synonyms (2)

7
votes
0answers
71 views

Find the recurrence formula for $\int \frac{dx} {(1+\sin x)^n}$

$$\int \frac{dx} {(1+\sin x)^n}$$ I know that I should use the following step: $$\int\frac{\sin^2(x)\, dx}{(1+\sin x)^n} +\int\frac{\cos^2(x)\, dx} {(1+\sin x)^n} $$ but here I get stuck. I do not ...
0
votes
0answers
52 views

A(n) = A(n-2) - nA(n-1) general formula?

I was working on a problem involving a continuous fractions. To solve the problem i would need to find a general formula for this sequence as a function of the two initial values A(1) and A(2). ...
0
votes
1answer
67 views

How do I find a recurrence relation?

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and ...
-1
votes
1answer
50 views

Find $u_3$ of recurrence relation $u_{n+1} = 0.2u_n + 9$ when only $u_5$ is known [closed]

A sequence is defined by the recurrence relation $u_{n+1} = 0.2u_n + 9$, ${u_5 = 11}$. What is the value of ${u_3}$? I have not encountered a problem like this when only one value for n is ...
1
vote
2answers
37 views

Finding a combinatorial recurrence relation with three variables

This question is from the generating functionology textbook, Let $f(n, m,k)$ be the number of strings of n $0$’s and $1$’s that contain exactly $m$ $1$’s, no $k$ of which are consecutive. Find a ...
1
vote
0answers
23 views

Symbol for Sequential Subtraction

I was just curious that why there is no symbol for sequential subtraction in maths. This is unlike summation and Multiplication? Each having their respective symbols as $\Sigma $ and $\Pi$, namely.
1
vote
1answer
46 views

Linear Non Homogeneous recurrence relation

Find the explicit formula for given recurrence relation: $$a_{n}-7a_{n-1}+10a_{n-2}=2n^{2}+2$$ With the initial conditions $a_0=0,a_1=1$. I just want to know whether the particular solution will be ...
1
vote
1answer
36 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
37 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
32 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
32 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
85 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
240 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
19 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
16 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
86 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
32 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
110 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
14 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
88 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
111 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
61 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
58 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
29 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. ...
8
votes
1answer
58 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
61 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
27 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
60 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
18 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
14 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
30 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
147 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
12 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
28 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
61 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
28 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
10 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
45 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
138 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
30 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
0answers
58 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, ...
0
votes
0answers
26 views

How to solve this type of recurrences?

How to solve the recurrence $g(x,y) = g(x-y+1,y) + g(x-y+1,y-1)?$ Here especially the $x-y+1$ term has been giving major problems as I have no idea how to go about it. Boundary : $x \geq 3$ and $y ...
1
vote
2answers
55 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
76 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
43 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
48 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
62 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: ...
1
vote
2answers
49 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
55 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 ...