induction – Every AVL tree can be colored to be a red-black tree

I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately.
Let $h$ be the height of a subtree of an AVL tree.
It is given that such a coloring is constrained by these cases:

  1. $h$ odd $implies$ black height $=$ $frac{h}{2} + 1$, root node black
  2. $h$ even $implies$ black height $=$ $frac{h+1}{2}$, root node red

After that the root node is colored black.


I’m trying to prove this inductively. Let’s start with the base case $h=1$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.

Now suppose the statement is true for some $h geq 1$. Then for any node $u$ in the AVL tree, the height difference between their children is less than $1$. That is, for an AVL tree of height $h+1$ either both subtrees of the root node have height $h$ or one has height $h-1$.

By the induction hypothesis we know how to color the subtree of height $h$, depending on the parity of $h$. I’m unsure if I should use strong induction instead because it is not given in the hypothesis how to color a subtree of height $h-1$.

If we would know how to color both subtrees, then consider the following cases:

  1. $h+1$ is even
    • one subtree has height $h$, the other height $h-1$
    • both subtrees have height $h$
  2. $h+1$ is odd
    • one subtree has height $h$, the other height $h-1$
    • both subtrees have height $h$

For case 1.1 we would get
$$
begin{align*}
quad & h+1 &text{even} \
implies quad & h &text{odd} \
implies quad & text{black height} = frac{h}{2} + 1 \
implies quad & h-1 &text{even} \
implies quad & text{black height} = frac{(h-1)+1}{2} = frac{h}{2}
end{align*}
$$

So their black heights differ by $1$. How would I take that into consideration?

logic – how to prove equivalence of two substitutions by induction

I’m trying to prove the following reduction
t{x:=u}{y:=v} = t{y:=v}{x:=u{y:=v}}
We have the following Assuming:
(1)($x neq y$ )

(2)x is not a free Variable of v (i.e $x notin $fv$(v)$🙂

My idea is to do it by induction, but I’m a bit stuck with the base case. I would appreciate if someone can explain to me how to such a proof. I’m including what I tried (but it’s wrong/incomplete)

*Base case*: Assuming t is a just a variable `m` (t=m),
#on the left side we have
if m = x ==> u{y:=v}  (if u=y then `v`  else `u`)
else   ==> m{y:=v} (if m=y then `v`  else `m`)

#On the right side
if m=y ==> v{x:=u{y:=v}}  (if u=y then `v{x:=v}`  else `u{x:=u}` ( so we get either (v=x==> `v` else `v`) or else u=x==> `u` or else `u`) ) 
else   ==> m{x:=u{y:=v}} (if m=y then `m{x:=v}`  else `m{x:=u}`( so we get either v or m))

I understand we end up getting the same four branches, but is that considered really a proof? Is this the proper way to write such proof and conclude for the base case? Also the given assumptions didn’t help much here so I think I’m missing the part where I need to use those assumptions…

I think once the base case is proven,

we can do the following

case t = ($t_{1}$$t_{2}$)

t{x:=u}{y:=v} ==> t1t2{x:=u}{y:=v} 
==> t1{x:=u}{y:=v} t2{x:=u}{y:=v} and we have just proven in the base case that:
t1{x:=u}{y:=v} = t1{y:=v}{x:=u{y:=v}}  and  t2{x:=u}{y:=v} = t2{y:=v}{x:=u{y:=v}} 
so  t1{x:=u}{y:=v} t2{x:=u}{y:=v} = t1{y:=v}{x:=u{y:=v}} t2{y:=v}{x:=u{y:=v}} 
= t1t2{x:=u}{y:=v} = t1t2{y:=v}{x:=u{y:=v}} 

Now only part left is if $t= lambda m . t$

so we have $(lambda m . t)${x:=u}{y:=v}
this can be directly re-written as $lambda m . t${x:=u}{y:=v}, which is the base case again…

Could someone please help ne finish this proof correctly and explain to me the right way to do it?

Thanks in advance

functional programming – Lambda calculus list encoding, proof by induction

I’m new to functioanl programming. I’ve been looking into lists and list encoding. I was looking for some exercies online and came across the following, I struggled to understand how to approach it:

List encoding

The terms Lm and L′m for each natural number m are defined . (Note that n and c are variables while m stands for a number or its Church encoding.)

L′0 = n
L′m = c m L′m−1 for m > 0

Lm = λc.λn.L′m for any m

Q: Prove by induction on m that

enter image description here

I feel like I’m missing something as I cant work out what the proof by induction would look like. How would the factorial function be added in?

enter image description here

induction – Bound on subsequent terms of inductively defined sequence

Let $(a_n)$ be the sequence defined by $a_0=1$ and $a_{n+1}=frac{a_n}{2} + frac{1}{a_n}$. Show that $|a_{n+1}-a_n|=(frac{1}{2})^{n+1}$.

Using the induction hypothesis I can show that

$$|a_{n+1}-a_n|leq frac{|a_n-a_{n-1}|}{2} + |frac{1}{a_{n-1}}- frac{1}{a_n}|leq (frac{1}{2})^{n+1} + |frac{1}{a_{n-1}}- frac{1}{a_n}|.$$

I cannot get rid off the extra term and I have tried different approaches, but this one seems like the most promissing one because the bound appears naturally. I think I am missing something obvious.

Thank you.

induction – can you help me to prove this?

Thanks for contributing an answer to Mathematics Stack Exchange!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

asymptotics – Recurrence relations and induction: guessing the right bound

For sure, $T(sqrt{n})leq T(n)$, so $T(n)leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful.

Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(sqrt{n})=O(n)$, so also the solution of $T(n)=T(sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$.

I have to admit that this approach doesn’t seem (also to me) very formal, so I’ve confirmed that guess by explicit calculation.
Indeed, suppose $T(n)=an^2+bn+c$, then $T(sqrt{n})+T(n-1)+n=an^2+(1-a)n+bsqrt{n}+a-b+c$: we have equality if $a=1$, $b=0$ and $c=-1$, so $T(n)=n^2-1$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $T(1)=0$; in general you have to check that $T(n)=O(n^2)$ (actually, $T(n)=Theta(n)$) by induction.


So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth.
E.g., consider the recurrence $T(n)=T(n^{3/4})+T(n-1)+n$: if $S(n)=O(n^2)$, then $S(n^{3/4})=n^{3/2}$ is no more a $O(n)$, so we cannot conclude as before.
But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$
(with reasonable assumption of functions $f,g,h$, I mean, positive, monotone, …)
and the solution of, say, $S(n)=S(g(n))+O(h(n))$ is such that $S(f(n))=O(h(n))$, then you can make the (more than) reasonable assumption that $T(n)=O(S(n))$, and confirm it by induction.

complexity theory – Failing to solve a recurrence by induction

My question is strongly related to the one asked here:

How do I show T(n) = 2T(n-1) + k is O(2^n)?

$$T(n)=2T(n-1)+1$$

Going with the steps, I reached the point where:

$$c*2^{n}geq c*2^{n}+1$$
which implies
$$0geq 1$$
which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.

However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don’t understand how should I be able to justify that, is this a scenario in which “induction fails” ? because I’ve never heard of such one.

proving summation using induction

we need to prove that for ever $n∈N$ the following equality is right
$$frac{3sum_{i=1}^n i^5}{{sum_{i=1}^n i^3}} = 2n^2+2n-1$$
so first of i checked for n=1 and we get
$$frac{3sum_{i=1}^1 i^5}{{sum_{i=1}^1 i^3}} = 2*1^2+2*1-1$$ which is $3=3$

now I assume for $n=k$

$$frac{3sum_{i=1}^k i^5}{{sum_{i=1}^k i^3}} = 2k^2+2k-1$$
and next is to solve for $n=k+1$
$$frac{3sum_{i=1}^{k+1} (i^5)}{{sum_{i=1}^{k+1} i^3}} = 2(k+1)^2+2(k+1)-1$$

$$frac{3sum_{i=1}^{k+1} (i^5)}{{sum_{i=1}^{k+1} i^3}} = 2k^2+6k+3$$

now I tried to separate the $sum_{i=1}^{k+1}$

$$frac{3sum_{i=1}^{k} (i^5)+{3sum_{i=k+1}^{k+1} (i^5)}}{{sum_{i=1}^{k} i^3}+{sum_{i=k+1}^{k+1} (i^3)}} = 2k^2+6k+3$$

now since $$frac{3sum_{i=1}^k i^5}{{sum_{i=1}^k i^3}} = 2k^2+2k-1$$ i tried putting it instead of what i have in the fraction and i got stuck

$$frac {2k^2+2k-1+{3sum_{i=k+1}^{k+1} (i^5)}}{{sum_{i=k+1}^{k+1} (i^3)}} = 2k^2+6k+3$$

sorry for my English mistakes hope it is understandable , appreciate any help and tips!

lo.logic – Peano axioms- Exponentiation only using the induction axiom and without the recursion theorem

The Peano axioms of $Bbb N$ are:

  1. $1 in Bbb N$, i.e. $Bbb N$ is not empty and contains an element denoted by $1$.

  2. Every natural number has a successor, i.e. $forall ninBbb N, exists!s(n)inBbb N$.

  3. if $s(n)=s(m)$ then $n=m$.

  4. $1inBbb N$ is the only element that is not the successor of a natural number.

  5. The axiom of Mathematical Induction is valid:

    Let $SsubseteqBbb N$ such that

    1. $1in S$

    2. $forall ninBbb N,nin SRightarrow(s(n)in S)$.

    Then $S=Bbb N$.

Question: Is it possible to define exponentiation $a^n$ using only axioms 1, 2, 5? Thus, I would like to define a binary operation on $Bbb N$ that satisfies $a^1 = a$ and $a^{n+1} = a^n cdot a$.

In every book I have available to me, the standard way to define exponentiation uses the recursion theorem. But, the proof of the recursion theorem uses all five axioms, so I cannot use the recursion theorem in my case. However, exponentiation seems like it should be definable since it is possible to define addition and multiplication using only axioms 1, 2, 5.

Is it possible to define $a^n$ and is there an elementary proof of this, a proof that uses only axioms 1, 2, 5, addition and multiplication, and nothing else?

co.combinatorics – Union closed conjecture induction

I would like an example showing that one of the most basic induction approaches to the union-closed conjecture fails. If, for any union-closed family $mathcal{A}$ of subsets of a finite set $X$, there is some $x in X$ such that each $y in X$ has $|{A in mathcal{A} : A ni y text{ and } A ni x}| ge frac{1}{2}|{A in mathcal{A} : A ni x}|$, then we can merely use induction applied to the union-closed family ${A in mathcal{A} : A not ni x}$ to get some $y in X$ in at least half of the sets of ${A in mathcal{A} : A not ni x}$, and by our choice of $x$, we then see that $y$ is in at least half the sets of $mathcal{A}$.

I have to think that there is a known example showing this approach doesn’t work, i.e., there is an $mathcal{A}$ with no such $x$. But I couldn’t think of an example. So,:

Give an example of a finite set $X$ and a union-closed family $mathcal{A} subseteq mathcal{P}(X)$ such that, for each $x in X$, there is some $y in X$ with $$|{A in mathcal{A} : A ni y text{ and } A ni x}| < frac{1}{2}|{A in mathcal{A} : A ni x}|.$$ (Or prove the union-closed conjecture!)

I avoid degenerate cases, like $X = emptyset$, $mathcal{A} = emptyset$, or $mathcal{A} = {emptyset}$.