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

learn more… | top users | synonyms (2)

1
vote
0answers
53 views

How to solve even/odd divide-and-conquer problems?

I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to ...
1
vote
1answer
33 views

Number of colorings under cyclic permutation.

Given $\lambda\vdash n$. How many ways to color $n$ beads of chaplet into $l$ colors, such that $\lambda_1$ of $1^{st}$ color, $\lambda_2$ of $2^{nd}$ color, etc. For, examples if $\lambda=(3,2)$, ...
0
votes
1answer
398 views

A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)? I get somewhere T(n) = Θ(n^2), is that correct?
3
votes
2answers
170 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
1
vote
1answer
66 views

a nonlinear difference equation limit

let $$a_1=1, a_{n+1} = a_n + \frac{1}{a_n^2}$$, and it seems $$\lim_{n\to\infty} (a_n^3-3n-\log n) = \text{C}(constant) $$ I use computer program to verify that $$C = 1.13525585...$$,and expecting ...
1
vote
1answer
42 views

Is this true of all linear recurrences?

Is it true that any linear recurrence $f_n$ can be written as: $$f_n = \sum_{i=1}^{k} \alpha_i r_i^n$$ where $f_n$ is a linear recurrence of degree $k$ and $r_i$ represents a root of the ...
0
votes
1answer
34 views

Is my generating function correct so far for this recurrence?

Trying to teach myself generating functions. Recurrence: $a_n = 18a_{n-1} - 80a_{n-2}$ where $a_0 = 1$ and $a_1 = 9$. Attempt at using generating functions: $$G(x) = \sum_{n=0}^{\infty} a_nx^n \\ G(...
0
votes
3answers
32 views

Compressing two recurrences

I have two recurrences $a_n = 9a_{n-1} + b_{n-1}$ $b_n = 9b_{n-1} + a_{n-1}$ Is there a way to combine these two so it's only in terms of $a_n$? $a_1 = 9, b_1 = 1$, if this information is needed.
1
vote
0answers
19 views

Oscillations in a Discrete Dynamical System.

If you are familiar with SingingBanana on youtube, he posted the following question: There is a 10 digit number where the first digit tells me how many 0 there are in the number, the second digit ...
1
vote
0answers
39 views

How to correctly set up inductive proofs?

In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence $0, 1, ...
0
votes
3answers
33 views

Not Deducing a Closed Form for Recurrence Relation Correctly

Here is a recurrence relation $$a_1 = 2$$ $$a_{n+1} = \frac{1}{2}(a_n + 6)$$ where $n \in \mathbb{N}$. For hiccups and giggles, I wanted to determine a closed form for the recurrence relation. ...
1
vote
0answers
31 views

General periodic recurrences

I was blown away when I read in Concrete Math that the recurrence $$Q_0 = \alpha$$ $$Q_1 = \beta$$ $$Q_n = \frac{Q_{n-1} + 1}{Q_{n-2}}$$ is periodic (period 5). Is there a general method to determine ...
0
votes
0answers
33 views

lotto draws- calculate the number of successes in full growth

In my country we have a special lottery There are 45 numbers and you can choose as many as you like in order to get right the 5 winning numbers. For example you can choose 10 out of the 45 numbers ...
1
vote
1answer
107 views

An optimal sequence of length 13

I'm looking for an optimal (or much better than I have now) increasing sequence $t_1, t_2, .., t_{13}: t_i \in N, 0 \le t_i<t_{i+1}$ where $3t_{12} + 4t_{13}$ is minimized, subject to the ...
1
vote
1answer
46 views

Why can't this be done with Master Theorem

Apparently recurrences like this cannot be solved with the Master Theorem: $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$ Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) ...
1
vote
2answers
42 views

How to analyze the time complexity $\Theta$ of this recurrence

I am trying to understand how to show that $$T(n) = T(n/2) + T(n/4) + n^2$$ is $\Theta(n^2)$ by using a recursion tree. I tried substitution at first but it got real messy real fast. This is self-...
0
votes
0answers
58 views

Is exponential decay a moving average filter?

I learned that a moving average filter is an FIR filter that gives the average of $N$ previous inputs, like this: $y_n = \sum_{i=0}^{N-1}\frac{x_{n-i}}{N}$ As a simple extension, it might be some ...
2
votes
2answers
57 views

number of ternary trees: finding a recurrent relationship

If $t_n$ is the number of ternary trees with n nodes, with $t_0=0$, what would be the convenient manner for finding a recurrent relationship for $t_n$? It is given that $t_1=1, t_2=3, t_3=12$. A ...
0
votes
1answer
44 views

Closed form solution for recurrence relation with 2 variables

Please help me in finding the closed form solution for the recurrence relation : \begin{align*} f(n, d) &= 2 \sum\limits_{i=1}^{n-1} f(i, d-1) + f(n, d-1) \\ & \text{for $n > 1, d > 1$} \...
2
votes
0answers
48 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where $l$...
2
votes
2answers
49 views

Recurrence relation - How To Give a Combinatorial Proof

Problem: Consider the set $S$ of all “ternary strings” (strings in the ‘alphabet’ {$0$, $1$, $2$}), such that a $0$ never is directly followed by a $1$ or a $2$. (Thus, e. g. the strings $12100$ and ...
1
vote
0answers
45 views

Proof that common differences imply a polynomial-generated sequence

I have long been familiar with the method of common differences for finding the equation of a sequence: you subtract consecutive terms going down level by level, until you get a constant difference at ...
0
votes
2answers
96 views

Perplexing integral

First and foremost, is it possible to get the integral you are trying to solve as the solution? I just got the same integral twice. I have also tried MATLAB but it gives the same result. Below is the ...
0
votes
0answers
37 views

A particular recursion

Given $s_0=2^r>0$ let $s_i=\frac{s_{i-1}}{2^{\log^c{r_{i-1}}}}$ where $c\geq1$ and $r_{i+1}=\log_2(s_{i+1})=r_i-(\log_2(r_{i}))^c\leq r_{i}$. What is the value of smallest $i$ at which $s_i<1$ ...
3
votes
1answer
74 views

Convergence of sequence of ratio of consecutive terms.

I would like to prove that the following sequence of ratios $(x_n)$ where $x_n = c_n/c_{n-1}$ converges to a finite limit $L$: $$\lim_{n\to\infty} x_n = \lim_{n\to\infty}\frac{c_n}{c_{n-1}} = L$$ ...
9
votes
0answers
82 views

How to 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 ...
0
votes
0answers
56 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). $$A(n)...
0
votes
1answer
72 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 (...
0
votes
1answer
52 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
41 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
25 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
57 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
55 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 \sum_{i=1}^{h-...
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
47 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
263 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
23 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
25 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
98 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
43 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\| = \...
3
votes
5answers
119 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
78 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
65 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
67 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 ...