The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
8 views

Using a recursion tree to obtain an algorithm classification with n^2 time

I'm having trouble getting the classification of this recurrence relation using a recursion tree. $$T(n) = 3T(n/2) + n^2$$ I have the tree written out correctly (I hope): ...
2
votes
1answer
26 views

Imaginary solutions of a recurrence relation

How to solve this recurrence relation using characteristic equation and imaginary numbers? We have $a_0 = 0$ and $a_1 = 1$ , and for all $j\in\mathbb N$: $$a_{j+2} = 6a_{j+1} - 10a_j$$ I would ...
0
votes
3answers
43 views

Solve recurrence relation problem

This is a recursion problem that I am stuck at. I need to use the characteristic equation. Let $a_0, a_1, a_2, . . .$ be defined by $a_0 = 5, a_1 = 0$, and $a_{n+2} = a_{n+1} + 6a_n$ for $n \ge 0$. ...
0
votes
2answers
32 views

If $T(0) = 0$ and $T(n>0) = 2T(n-1)+4^n+1$, what is the explicit formula (via recursion)?

All I know is that you'd have to use substitution to get rid of $T(n-1)$ and summations for the rest, but whenever I work through it I get to $2^{(n+2)}+2^{(n-1)}-2.5$ which is not the correct answer ...
1
vote
0answers
18 views

Approximate Solution to Backwards Recurrence of Dynamic Game

Suppose we keep tossing a fair dice until we reach some cumulative sum greater than or equal to $N$. Then, let $S_k$ be the expected value of the final sum, given that the current sum is $k$. We have ...
0
votes
1answer
20 views

Recursive sort that doesn't require list splicing?

I was just wondering if there was some form of sort algorithm that doesn't require any form of splicing of the original list? Thanks in advance.
5
votes
2answers
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
1
vote
1answer
29 views

How does mathematics fit into fractal generation for computer graphics?

I have to do a research paper on any mathematical concept. The mathematical concept must be complex, so I thought fractals would be a good choice (I was told it was a complex idea). I have been ...
1
vote
1answer
29 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
1
vote
0answers
41 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
0
votes
2answers
27 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
0
votes
2answers
63 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
46 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
0
votes
1answer
57 views

Recursion: Dividing n people into groups of 1 or 2

Let $n \ge 1 $be an integer and consider $n$ people $P_1, P_2, . . . , P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group consists of either one ...
0
votes
0answers
8 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
0answers
27 views

Prove using Induction : Recursion

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
0
votes
2answers
68 views

Recursion: putting people into groups of 1 or 2

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
2
votes
2answers
35 views

Proving a Recursion Using Induction

I am trying to prove the following recursion. $$a(n) = \left\{\begin{matrix} n(a(n-1)+1) & \text{if } n \geq 1\\ 0 & \text{if } n = 0 \end{matrix}\right.$$ is the series definition of ...
0
votes
1answer
16 views

Substitution method for solving recurrences piece wise function

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$
0
votes
1answer
59 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...
2
votes
3answers
109 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
1
vote
1answer
51 views

Does the existence of a recursive sequence that involves an arbitrary choice at every step require the axiom of choice?

Say I want to define a sequence $(x_n)$ recursively, and at each step I make an arbitrary selection for $x_{n+1}$ out of some nonempty pool of acceptable candidates dependent on $x_n$. Does the ...
0
votes
1answer
111 views

Recursive Sequence Ratio Convergences

I would like to propose a conjecture (I haven't found any ressources covering my hypothesis): Let $X$ be a recursive sequence of the form \begin{equation*} X_n = \sum_{i=n-a}^{n-1} X_i ...
1
vote
2answers
41 views

Are there real extensions of the operations of addition, multiplication, exponentiation, etc in the other direction?

We have $\underbrace{a+a+a...+a}_{n\:times}$ which equals $a \times n$, and also $\underbrace{b \times b \times b.... \times b}_{p\: times}$ is $b^p$, so I was wondering if the generalization would ...
2
votes
1answer
48 views

Strong induction on a summation of recursive functions (Catalan numbers)

I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction: $$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$ Some cases: S(0) ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
3
votes
0answers
27 views

When do Leibniz-like rules lead to unique linear operators

Background Usually one defines differentiation in terms of limits, and then shows that differentiation satisfies the Leibniz (product) rule, $$\frac{d}{dx}(f \cdot g) = f\frac{dg}{dx} + g ...
0
votes
1answer
29 views

Definition of factorial function for sets

Why is the factorial function expressed in terms of $(n+1)$ for sets? $0! = 1$ $(n+1)! = (n+1) \times n! $ for all $n$ $\in\mathbb{N}$ Instead of the more "common" $0! = 1$ $n! = n \times (n-1)!$ ...
0
votes
1answer
35 views

Sinewave riding on sinewave help

Consider this image Top one is Cos(t), I know that. What is the equation for the second one? (sinewave within sinewave) And how would I get to the third one and then on n-amount of recursion? Mind ...
1
vote
2answers
57 views

Natural numbers object via initial morphism

I assume that a natural number object (or see nLab) can be defined as an initial morphisms. (edit: as in the title, I ment initial morphism, not objects) $\hspace{1cm}$ Thoughts: Probably $X:=1$, ...
0
votes
5answers
42 views

Recursive formula - alternating addition and suntraction

So i got this formula that basically does this: $$f(n) = n^2-(n-1)^2+(n-2)^2...$$ until it gets to $f(1)$ which is $1$. The recursive form is: $$f(n)=n^2-f(n-1)$$ So is there a way to get to the ...
1
vote
2answers
42 views

Converting Recursive Function into Closed/Explicit Form

so I have this recursive function here: $\forall n>1,f(n) = 2(f(n-1)) + n-1$, (where it is $0$ when $n$ is less than $1$) So I have tried to use iteration for this but it just gets more ...
0
votes
1answer
43 views

A question about numbers with a certain property

Find (if exists) a subset of the non negative integers $X$ such that for every non negative integer $n \in \mathbb{N}\cup\{0\}$ there is exactly one solution of the form $a+2b=n$ with $a,b \in X$ I ...
1
vote
2answers
22 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
2
votes
5answers
27 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
0
votes
3answers
40 views

Finding a recursive formula for a number

I am trying to find a recursive formula for a given number in order to solve a problem I am working on. For every $n \in \mathbb{N} \setminus \lbrace 0,1 \rbrace$ we define the number ...
3
votes
3answers
117 views

Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...
2
votes
1answer
69 views

Recurrence vs Recursive

Say team 1 is studying the recursive characteristics of a function. Team 2 is studying the recurrent characteristics of the same function. Are the 2 teams studying the same thing? I have found for ...
0
votes
0answers
33 views

How to model equation system involving recursion?

It is trivial to solve for the "chocolate wrapper" problem using a computer, and a loop: Little Bob loves chocolates, and goes to a store with \$N in his pocket. The price of each chocolate is ...
0
votes
0answers
13 views

Recursion, Induction, and Vinogradov Notation

I have a recursion relation $$ S(x, p_{n+1}, k) = S(x, p_n, k) - c(p_n) S\bigg(\frac{x}{p_n}, p_n, k p_n\bigg) + S\bigg(\frac{x}{p_n^2}, p_n, k p_n^2\bigg) \quad $$ where $c(l)$ are constants such ...
1
vote
2answers
53 views

Structural Induction help

Give a recursive definition of the set of bit strings that contain twice as many 0s as 1s. please any guidance would be appreciated this is a hw problem.
2
votes
1answer
38 views

prove a recursive function by induction

I have a homework assignment that requires me to prove a recursive function through induction. It seems like that I am stuck on simple algebraic properties and I can't figure it out... If you can, ...
1
vote
0answers
14 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
0
votes
1answer
54 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? ...
5
votes
0answers
44 views

One Simple Code and Problem on Running [closed]

My Stackexchange friends, would you please show the following code how manipulate the n-elements array A?
2
votes
1answer
24 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
1
vote
1answer
39 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
47 views

Arithmetic Turing machines

Consider the family $T_{1}$ of Turing machines with two tape symbols $b,1$ ($b$ the blank symbol). The family $T_{1}$ is Turing complete. Identify the tape with $\mathbb{Z}$ and let $0\in \mathbb{Z}$ ...
6
votes
2answers
188 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
3
votes
2answers
37 views

Number of $1$s in the binary representation of $n$

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition: $$b(n)=m :\equiv (\exists k_1\dots ...