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

learn more… | top users | synonyms (2)

1
vote
1answer
73 views

Segner's Recurrence Relation [closed]

Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it? I can't seem to understand why this formula works/is true. $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots ...
1
vote
1answer
35 views

How do I create a function from this code? [closed]

Here is the code: for (int i = 1; i < n; i *= 2) ++k; I need to express this as a function. I don't know where to begin.
1
vote
2answers
39 views

$n$th derivative of $e^{-x^2}$

I observed that $f^{(n)}(x)= \begin{cases} e^{-x^2} & \text{if $n=0$}\\ -2xe^{-x^2} & \text{if $n=1$}\\ f^{(n-1)}(x)-f^{(n-2)}(x) & \text{otherwise.} \end{cases}$ How to get the closed ...
1
vote
1answer
61 views

Properties of a recursively-defined sequence using induction

This is a homework problem. Not expecting the solution, just a nudge in the right direction! $N$ is a function defined inductively as follows: $$N(1) = N(2) = N(3) = 1$$ $$N(n) = N(n−1) + N(n−3) ...
-1
votes
1answer
65 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
2
votes
2answers
50 views

Help with a recurrence relation

I have been battling with the following: $$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$ I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving ...
0
votes
1answer
27 views

Why does the sign change here?

They give the recurrence relation as: $$T(n) − 4T(n − 1) + 3T(n − 2) = 0,\ T(0) = 0,\ T(1) = 2$$ And then they say it can be written as the following for $n > 1$: $$T(n) = 4T(n − 1) − 3T(n − 2)\ ...
1
vote
2answers
36 views

Help with proof by induction

The author generates a Tower of Hanoi and looks at the sequence: $$1, 3, 7, 15, 31, 63,...$$ He guesses the recurrence relation from the first few terms: $$H_{n} = 2^{n} - 1$$ Now he wants to ...
1
vote
3answers
49 views

recurrence relation of a finite sequence

Suppose I have a sequence of vectors $v_1,v_2,\ldots,v_n$ and for $k=1,2,\ldots,n-2$ $$v_{k+2}=av_{k+1}+bv_k, \quad a,b\in \mathbb R.$$ Can I deduce that $v_{k}=Ax_1^k+Bx_2^k, k=1,2,\ldots,n$ in which ...
1
vote
0answers
12 views

Is there a way to express a closed form for a partial derivative of this recurrence relation?

Here's the relation: if $n\ge j:$ then $$ \sigma(n,j,d) = d \cdot\left( \log j-\sigma\left(\frac{n}{j}, 1+d, d \right)\right)+\sigma(n, j+d, d )$$ And here's the terminating condition if $n < j$ ...
0
votes
1answer
40 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
1
vote
2answers
74 views

How does this simplification work?

The following recursive function was given: $$T\left(n\right) = T\left(n - 1\right) + x$$ The author stated that by using repeated substitution we can solve the recurrence relation: The basic ...
0
votes
1answer
30 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
0
votes
1answer
55 views

Find the difference equation for {2, 4, 16, 256, …}

Write a difference equation to represent the change during the nth interval as a function of the previous term in the sequence. b. {2,4,16, 256,...} I know that an= 22n but I can't figure out how to ...
0
votes
1answer
50 views

Which case of the Master theorem applies to the recurrence $T(n)= 100T(n/99)+\log(n!)$?

How to use the Master theorem to solve $T(n)= 100T(n/99)+\log(n!)$? I was given this question, and I can't figure out which case of the master theorem goes here. Thanks for your suggestions.
2
votes
1answer
70 views

Solving recurrence relation

If I have the following recurrence relation, $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n $$ How would I show that $T(n)\le cn\lg(n)+dn $ for some reals $c$ and $d$?
2
votes
1answer
62 views

The sequence $(a_0,a_1,a_2,\cdots,)$ satisfies $ a_{n+1}=a_n+2a_{n−1}$. What is $a_5$?

Assume that the sequence $(a_0,a_1,a_2,\cdots,)$ satisfies the recurrence $\displaystyle a_{n+1}=a_n+2a_{n−1}$. We know that $a_0=4$ and $a_2=13$. What is $a_5$? I got $a_1=5, a_3=23, a_4=49, a_5=95$ ...
1
vote
0answers
40 views

Finding Function Representation of Recursive Sequence

I was trying to find one of the roots of $x^2 + 4x + 3 = 0$ by deriving a continued fraction from the recursive formula $x = -3/x - 4$ (every step of the approximation you increase the recursion by ...
0
votes
1answer
51 views

On the existence/applications of infinitely-nested functions

Inside a previous question, one particular nested function shown is the known tetration. This "kind" of arbitrary repeated functions has always intrigued me, because inside their properties lie so ...
1
vote
1answer
43 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
0
votes
0answers
42 views

Does $f(n,z)$ have $2^n$ distinct fixpoints $z$ for all $n$?

Let $f(z)$ be a given degree $2$ polynomial. Let $n$ be a positive integer. Let $f(1,z) = f(z)$ and $f(n,z)= f(1,f(n-1,z))$. How to decide if $f(n,z)$ has $2^n$ distinct fixpoints $z$ for all $n$ ?
2
votes
1answer
434 views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the ...
4
votes
2answers
34 views

Solve $T(n) = 1 +\sum_{i=0}^{n-1}T(i)$

For the recurrence defined by $$T(n) = 1 +\sum_{i=0}^{n-1}T(i)$$ Apparently $T(n) = 2^n$ .. but I cannot see it. This recurrence pops up during analysis of the Rod Cutting Problem. I keep looking to ...
2
votes
1answer
59 views

How prove there exist postive integer $n$ such $x_{n}>y_{n}$

let two positive sequence $\begin{cases} x_{n+2}=x_{n}+x^2_{n+1}\\ y_{n+2}=y^2_{n}+y_{n+1} \end{cases}$ and $x_{1}>1,y_{1}>1,x_{2}>1,y_{2}>1$ show that: there exists $n$, such ...
6
votes
0answers
122 views

Mathematics of the Ice Bucket Challenge

I've been considering the mathematics of the now global ice bucket challenge. Simple model In the simplest incarnation, there is one original seed, who then nominates 3 others, each of which take ...
1
vote
1answer
58 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
2
votes
1answer
31 views

Intersection of two recurrences.

I have two sequences obtained by recurrences: $$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$ $$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$ How can I prove that apart from $f(0) = g(0) = 1$, these ...
0
votes
2answers
110 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
2
votes
0answers
28 views

Solution of partial difference equation

I want to find the explicit solution of the following difference equation $e_{i,j+1}=re_{i-1,j}+(1-2r)e_{i,j}+re_{i+1,j}+km_{i,j}$ where $r>0$, $k>0$ and $m_{i,j}$ are known and $e_{i,0}=0$. ...
5
votes
4answers
100 views

Homework | Find the general solution to the recurrence relation

A question I have been stuck on for quite a while is the following Find the general solution to the recurrence relation $$a_n = ba_{n-1} - b^2a_{n-2}$$ Where $b \gt 0$ is a constant. I don't ...
1
vote
1answer
50 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
10
votes
5answers
787 views

How to deduce a closed formula given an equivalent recursive one?

I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially? For example: $$ f(n) = 2 f(n-1) + 1 $$ I know ...
2
votes
2answers
54 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
0
votes
1answer
57 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
0
votes
0answers
33 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
-1
votes
2answers
164 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
0
votes
1answer
61 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
1answer
25 views

Solving a recurrence relation with absolute values in it.

The recurrence relation is: Let $\{y_{j}\}_{j\in \mathbb{N}}$ be a sequence of integers and x a real number then define: $P_{1}(x):=y_{1}+(-1)^{1}|x-y_{1}|$ and the general j-step as ...
0
votes
1answer
75 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
4
votes
1answer
118 views

After how many steps can compositions of $x\mapsto x+1$ and $x\mapsto x^2+1$ produce the same result starting from $1$ and $3$?

This problem is from a Turkish contest: Let $P(x)=x+1$ and $Q(x)=x^2+1$. Consider all sequences $(x_k,y_k)$ such that $(x_1,y_1)=(1,3)$ and $(x_{k+1},y_{k+1})$ is either $(P(x_k),Q(y_k))$ ...
4
votes
1answer
87 views

Period doubling bifurcation in a quadratic map

I am attempting the find $\mu$ for which the map $$x_{n+1} = \mu + x_n^2$$ undergoes a period doubling bifurcation. I understand that finding the fixed points of the map is the first step towards ...
1
vote
1answer
53 views

Two sequences defined by recurrence relations satisfy $x_n/y_n<\sqrt{7}$ for all $n$

Let $(x_n)_{n\geq 1}$ and $(y_n)_{n\geq 1}$ be two sequences such that: $$x_{n+1}=x_n^2+1 \quad \text{ and } \quad y_{n+1}=x_n y_n$$ with $x_1=2$ and $y_1=1$ Prove that for all $n$ ...
-1
votes
1answer
87 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
0
votes
0answers
25 views

n-th derivative of product

I am looking for a closed-form for the $n^{\text{th}}$ derivative of $$\beta_1 g_1 g_3 + \beta_2 g_2 g_3$$ if $$g_k^\prime = \alpha_k g_{k+1}$$ Here's what I have tried so far: \begin{align*} ...
1
vote
1answer
147 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
2
votes
0answers
59 views

How to solve this finite-difference equation?

How to solve the following finite-differences equation: $$f(x) = f(x-1) + f(x-\sqrt{2}), \quad x\in [\sqrt{2}, +\infty) \,?$$ Let's say $f(x) = f_0(x)$ for $x \in [0, \sqrt{2})$ is a given function. ...
1
vote
2answers
52 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
2
votes
0answers
45 views

Recurrence Relation with $n^{\frac{1}{2^k}}$ Square Root

I tried to solve this recurrence relation, like the following: $$ \\ T(n) = \begin{cases} T(\sqrt[2]{n}) + c, & \text{if }n \geq 2 \\ a, & \text{otherwise} \end{cases} \\\\ T(n) = ...
3
votes
2answers
142 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
1
vote
1answer
63 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...