The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
30 views

Mathematical Induction Recursion

Consider the recursion given by $f(n) = 2f(n−1)− f(n−2)+6$ for $n ≥ 2$ with $f (0) = 2$ and $f (1) = 4.$ Use mathematical induction to prove that $f (n) = 3n^2 −n+2$ for all integers $n ≥ 0.$
1
vote
2answers
58 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
2
votes
2answers
147 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
3
votes
1answer
60 views

How many arrangements of the digits 1,2,3, … ,9 have this property?

How many arrangements of the digits 1,2,3, ... ,9 have the property that every digit (except the first) is no more than 3 greater than the previous digit? (For example, the arrangement 214369578 has ...
0
votes
0answers
45 views

Can the method of generating functions be applied to linear recursions of order $>4$?

I just got in touch with the method of solving recursions with generating functions. However, even if it is not mentioned anywhere, it seems to me, this approach is not applicable for recursions of ...
2
votes
3answers
87 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
0
votes
0answers
45 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
1answer
34 views

Find a formula for a sequence of the following character strings

Given strings: 0, 020, 0208020, 0208020180208020, 0208020180208020320208020180208020, ... I have to write a C++ program that computes the nth string. My problem is ...
3
votes
1answer
99 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
12
votes
4answers
420 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1]\,$ satisfying $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the functional relation $$ f\big(2x-f(x)\big)=x, \tag{1} $$ for all ...
0
votes
1answer
43 views

Master's theorem applicability.

I have to find out if the following recurrence can be solved with the master theorem: $$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$ I have figured that, here, I have the third case because ...
3
votes
1answer
29 views

Can you prove this recursive multiple $n$-sided dice throwing statement?

Let $W_{s,r,n}$ be the total number of ways that the sum $s$ can be displayed after throwing $r$ number of $n$-sided dice. Define $$W_{s,0,n} = \begin{cases} 1, & \text{if s = 0} \\ 0, & ...
2
votes
2answers
64 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
4
votes
0answers
139 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
1
vote
1answer
33 views

Maths/Programming recursion question

I know this is a programming question but it seems to be more on the mathematical side ( recursion ) I was hoping someone would be able to explain it to me since it will probably be on my exam ...
3
votes
4answers
84 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
0
votes
2answers
26 views

Express recursive funtion in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
1
vote
1answer
57 views

On the size of a set of functions such that $f(i)\ne f(i+1)$ for every $i$ (and similar conditions)

For a finite set $A$,let $|A|$ denote the number of elements in the set $A$. (a) Let $F$ be the set of all functions $$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying ...
3
votes
1answer
51 views

Structure of partial recursive function over recursively enumerable guard

I read that the function $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$ is recursive if ...
0
votes
1answer
21 views

computer recursion same question but omitting defdef

Given the alphabet {a,b}, give a recursive definition for the language whose words don't contain the string aa. My solution is i) b ∈ L1 ii) if w ∈ L1, then so is wba, abw My question is should i ...
1
vote
1answer
37 views

Another recursive math question

Given the alphabet {def ghi}, give a recursive definition for the language whose words contain the string defdef. My solution is: i) def ∈ L and ghi ∈ L ii) if u = def and w ∈ L*, then so is uu, ...
0
votes
1answer
28 views

recursive definition of strings

I have been unable to find any examples that resemble this problem and I am having issues with recursion. Here is the problem: Give a recursive definition for the set of strings of letters a, b, c, ...
0
votes
2answers
56 views

Recursive definition attempt.

I have the following question: $\text{b) }$Give a recursive definition for the function $f:\Bbb N\to\Bbb N$ which calculates the following sum for any $x\in\mathbb N$: ...
1
vote
1answer
35 views

computer theory recursion

I am having a bit of trouble understanding recursion and would like a bit of guidance. Consider the recursively defined language, L1: i) x ∈ L1 and y ∈ L1 ii) if w ∈ L1, then so is wxw ∈ L1 I have ...
2
votes
3answers
45 views

Recursion definition

Give a recursive defintion of the following set: $\{ 5^m 7^n \mid m, n \in N \}$ I don't have the slightest idea how to approach this question, id be really grateful if someone could provide me with ...
-2
votes
1answer
36 views

Proof by induction help

I don't know the full process of induction, as it's one of the harder questions on my upcoming test papers I thought i'd attempt to get a basic understanding; in order to get a 1/2 marks out of the ...
0
votes
2answers
47 views

proof by induction question

I decided to try proof by induction without any help = ) so if someone could check it out, pretty sure it's unfinished or, well i'm not sure. Also, if possible, could you take a logical guess for how ...
0
votes
1answer
47 views

function proving with induction [closed]

I'm having trouble with the following past paper question : Consider the function $take: \Bbb N \to \Bbb N$ defined recursively as follows: Base case: $take(0) = 100$ Recursive case: ...
0
votes
2answers
27 views

Recursion function question again

http://vvcap.net/db/3RxO1KX2d4LxgD714Tyh.htp mult(x,y)= mult(x-1,y)+4 mult(0,4)=0 mult(1,4)=mult(0,4)+4 mult(2,4)=mult(1,4)+4 mult(3,4)=mult(2,4)+4 I'm not sure whether this is correct, but i think ...
0
votes
0answers
27 views

Closed form for a special recursion?

Does the recurrence relation $$ a(n+1) = a(n)^2 + 1,\quad a(1)=1, $$ have a closed form solution? I have tried hard to find it, but failed. Any ideas ? I am particular interested in prime ...
12
votes
1answer
158 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemples. How to calculate the number of circuits that ...
2
votes
1answer
74 views

Generalization of the Tower of Hanoi?

What is the least possible number of steps for the Tower of Hanoi with $n$ discs and an arbitrary number $k$ of towers? For example, Tower of Hanoi with $4$ towers, $5$ towers, etc.
0
votes
1answer
36 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
0
votes
3answers
128 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
0
votes
1answer
28 views

Defining substitution by structural recursion

For a term u, let $u{x\atop t}$ be the expression obtained from $u$ by replacing the variable $x$ by the term $t$. Define $u{x\atop t}$ by recursion on $u$. Not really sure how to start this one. ...
2
votes
1answer
49 views

Question about chebyshev polynomial

chebyshev polynomials are defined as such: $T_n(x)=cos(n*arccos(x))$ I'm asked to show that $deg(T_j(x))=j$ and that $T_0,T_1,T_2,...,T_n$ are an orthogonal basis of $\mathbb R_n[x]$. I think I can ...
0
votes
1answer
50 views

A setting in which Rice's theorem is not true

In my class we call a set of computable functions $A$ recursive if its indexing set $I_A=\{e\in\mathbb N:\phi_e\in A \}$ is recursive, where $\phi$ is some known Gödel numbering of the computable ...
1
vote
0answers
38 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...
0
votes
1answer
57 views

how I prove a valid recursion?

Determine whether is this a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined (valid recursion), find a formula for f(n) when ...
1
vote
1answer
59 views

Recursive Square Root Futility Closet

This post on Futility Closet the other day: http://www.futilitycloset.com/2013/12/05/emptied-nest/ asked for the solution to this equation: \begin{equation}\sqrt{x+\sqrt{x+\sqrt{x...}}} = ...
0
votes
2answers
70 views

An effective enumeration of recursive sets in increasing order

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function. ...
1
vote
1answer
135 views

All infinite recursive sets can be enumerated by an injective function

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective ...
1
vote
1answer
60 views

Let $x$ be a real number. To prove…

Let $x$ be a real number. Define the sequence $(x_n)_{n\ge1}$ recursively by $x_1=1$ and $x_{n+1}=x^n+nx_n$ for $n\ge1$. Prove that, $$\prod_{n=1}^\infty \bigg(1-\dfrac{x^n}{x_{n+1}}\bigg)=e^{-x}$$ ...
0
votes
0answers
14 views

Recursion relation for the coefficients of the series solution around x=0 [duplicate]

ODE: the equation is the following; $$y''' + x^2y' + xy = 0$$ y=y0x0+y1x1+...+ynxn I have written equations for y, y', y'' and y''' there are: y = SUM y_k * x^k y' = SUM y_k * k * x^(k-1) y'' = ...
1
vote
1answer
56 views

Primitive Recursion Functions (Programs)

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
0
votes
1answer
39 views

Combinatorics recursion question. [closed]

How many binary vectors of length n do not contain a sequence '001' ? Solve by recursion and explain your solution.
1
vote
1answer
46 views

Prove that for any $m, n \in\omega$ that (i) $m + 0 = m$, (ii) $m + n^+ = (m + n)^+$

I am getting repeatedly lost trying to approach this question: Prove that for any $m, n \in\omega$ that (i) $m + 0 = m$, (ii) $m + n^+ = (m + n)^+$ I can fairly well grasp the idea that the ...
0
votes
1answer
31 views

A question on combinatorics

Bob and Laura have bought an apartment, and are going to carpet the floor in the kitchen. The kitchen has size $2 \times n$, where $n$ is a positive integer. In how many ways can Bob and Laura ...
3
votes
0answers
49 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...