Where I can find example how prove red black tree?
Here is the obvious thing to try:


Prove that if you apply the insertion algorithm twice on an empty tree, then the resulting red-black tree has a red node (this also follows from the invariants of red-black trees).
Prove that if a red-black tree has a red node and you insert an element using the insertion algorithm, then the result red-black tree has a red node.


I don't know if this scheme works, but it's the most immediate way to apply induction.