The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
54 views

Is the proof of non-totality of a function $f$ trivial if $f$ is recursively defined only on a subset of $\Bbb N$?

I define a fuction $*$ in a recursive way on a subset of natural numbers (with subset I mean that is $*$ define in the second argument only for $\Bbb N-\{0,1\}$ in other words we have $*:\Bbb N ...
5
votes
1answer
90 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
1
vote
1answer
28 views

Recursive sum of squares of prime numbers

Perfect squares always have recursive sum of their digits(e.g. $361\rightarrow 10 \rightarrow 1$) as either $1, 4, 7$ or $9$. But if the perfect square is square of a prime number, except of $3$ . ...
2
votes
3answers
336 views

recursive digit sum of cubes of integers.

For every cube of an integer, the recursive sum of its digits , e.g. 729 -> 18 -> 9 etc. is always 1,8 or 9. With a computer program i checked this phenomenon up to 1000000000. In my prior ...
-1
votes
2answers
46 views

Define this recursively : $f(n) = 3n - 4$

Define this recursively : $f(n) = 3n - 4$ I thought this is how you recursively define a function? $f^{-1}(n): y = 3n-4$ $y+4 = 3n$ $f^{-1}(n) = (y+4/3)$ But the answer is $f(n) = f(n-1) + B$ ...
0
votes
0answers
31 views

Amount of sub-matrices created by Laplace expansion

I have created a program that solves a matrices determinant using the Laplace expansion method, and I was wondering if there is a equation which provides how many sub-matrices are created and used in ...
2
votes
0answers
51 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
2
votes
2answers
53 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
1
vote
1answer
31 views

Coloring a binary tree

Working through a problems practice coloring, I have found a problem that has me stumped. The problem states: For $n \in \mathbb{R}_{>o}$ the binary tree is defined recursively as follows. The ...
0
votes
1answer
59 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
1
vote
2answers
88 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
1
vote
2answers
109 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...
3
votes
3answers
50 views

Prove convergence and find the value of the limit of the sequence

Sequence $$a_{n+1}=(1+\frac{1}{3^n})a_n$$ $$a_1=1$$ The question asks to prove its convergence and find its limit. I have tried all the usual ways but am unable to solve it. The question also says ...
0
votes
1answer
28 views

Diagonalization out of partial recursive functions

So generally partial recursive functions don't diagonalize. But isn't this function an exception? $\phi(x)=\lambda_{x}(x)+1 $ if $\lambda_{x}(x)$ halts and $0$ else. Completely no clue... It seems ...
1
vote
0answers
22 views

Show $f(x)$ is partial recursive using the

So I want to show that the function $f(x)=0 $ if $x$ is even and not defined otherwise, is partial recursive using the $\mu$ operator (bounded search function, which is partial recursive). Plan is to ...
0
votes
4answers
36 views

Given n flips, what is the expected number of times the sequence HT shows up?

Suppose a fair coin is flipped $n$ times - what is the expected number of appearances of the sequence HT? I know it's $\sqrt n$, can anyone provide an explanation why this is true?
-4
votes
1answer
38 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
1
vote
2answers
72 views

Definition by Recursion: why is the existence part not (almost) obvious?

I saw the following statement. Let $H$ be a set, let $e\in H$ and let $k:H\rightarrow H$ be a function. Then there is a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that ...
0
votes
0answers
68 views

Kleene's recursion theorem

Would anybody be able to provide me (someone with little familiarity with the subject matter) with a bit of background to the Recursion Theorem and guide me towards some texts on its mathematical and ...
1
vote
1answer
31 views

How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically. Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: ...
2
votes
2answers
50 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
3
votes
4answers
47 views

Is this a correct recursive sequence definition?

Take this definition: Is this definition of $s_k$ for $k\ge2$ correct? $s_k=6a_{k-1}-5a_{k-2}$ but where does the $a$ term come from? The book swaps $a$ and $s$ interchangeably.
0
votes
2answers
16 views

Recursion, Explicit Equasion

Prove $\ a_{n}<2^{n} $ for every natural number n, where $\ a_{n} $ is defined recursively by $$ a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$$ Once I get the explicit ...
0
votes
2answers
48 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
45 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
1
vote
0answers
32 views

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be ...
2
votes
1answer
126 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
0
votes
1answer
27 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
0
votes
1answer
24 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
0
votes
1answer
31 views

How to deduce from a recursive variant of the triangular numbers the non-recursive form?

This is probably simple (if not, my apologies beforehand), but I have the following formula: $$f(0) = 2$$ $$f(x) = 6x + 2 + f(x -1) \; \text{ where } x \in \mathbb{N}_{\gt 0}$$ The formula actually ...
2
votes
0answers
86 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
1answer
25 views

proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
0
votes
1answer
29 views

Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I ...
-1
votes
1answer
49 views

Proof of a sequence with recursion

The problem asks to prove the following to be true. $$F^2_{n+1} - F_{n+1} F_n - F_n^2 = (-1)^n$$ Anyway, I've tried looking at this or similar proofs for going on an hour now, pretty much the only ...
1
vote
2answers
23 views

Question over recursive definitions

Let $E$ be the set of even integers. Then the Base Case: $0\in E$ And the constructor case would be If $n \in E$ then so are $n+2$ and $-n$. This makes sense. But would the Base case and constructor ...
2
votes
5answers
91 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
3
votes
2answers
49 views

$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$ $0<c<1$ and $T(1)$ is constant. My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong. My guess is that $T(n) = ...
3
votes
2answers
127 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
0
votes
1answer
43 views

Discrete Math Recursive Functions for Strings

Recursive Functions for Strings Construct a recursive definition for the following string function over the alphabet {x,y}: f(x) returns the string where every x is replaced by xy and every y is ...
0
votes
0answers
25 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
6
votes
3answers
197 views

Definition of General Associativity for binary operations

Let's say we are talking about addition defined in the real numbers. Then, by induction we define $\sum_{i=0}^{0}a_i=a_0$ and $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ for $n> 1.\:$ Now, how do ...
0
votes
2answers
55 views

Prove via induction this recursively defined sequence

Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$ Highly verbose solutions are greatly appreciated.
2
votes
1answer
197 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
0
votes
1answer
32 views

Show that the set of sets {$A_n$} has $n$ elements and that it is transitive

We define by recursion the set of sets {$A_n : n∈ℕ$} this way: $A_0 = ∅$ $A_{n+1} = A_n ∪$ {$A_n$}. I want to prove by induction that for all $n∈ℕ$, the set $A_n$ has $n$ elements and that $A_n$ ...
0
votes
2answers
88 views

Prove that a Fibonacci number is greater than $ φ^n$

How can I prove the following: If $f_n$ is a number of the Fibonacci sequence and φ= $\frac{1+\sqrt{5}}2$, then $f_n > φ^n$ for every $n >2$? I have tried using induction but I can't ...
0
votes
2answers
34 views

What is the general stragety for conjecturing a formula based off a pattern?

Is it simply to guess and evolve a answer until it gets closer or is there an approach? Ex: Find the formula for: $a_k = \frac{a_{k-1}}{2} + 1$ where $a_0 = 1$. One would go: $a_1 = 3/2, a_2 = ...
0
votes
1answer
23 views

How do you use induction on a recursive sequence using different variables?

I've been working on some recursive sequences for my Discrete class. I've understood most of them, but I've come to a new question which I'm confused about. A sequence $C_{0}$, $C_{1}$, $C_{2}$ is ...
0
votes
3answers
36 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
2
votes
0answers
60 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
1
vote
2answers
141 views

Convergence and limit of a recursive sequence

Let $p>0$ and suppose that the sequence $\{x_n\}$ is defined recursive as $$ x_1 = \sqrt{p}, \quad x_{n+1} = \sqrt{p + x_n}, $$ for all $n \in \mathbb{N}$. How can I show that $x_n$ converges, ...