A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes

Question

Let us call a red-black tree strict when every black node has at most one red child.

Show that a strict red-black full tree has at most $(n − 1)/4$ red nodes; a binary tree is full when every node has zero or two children.

The hint for this problem says to use a charging argument but I can't seem to figure one out.

My idea was to consider the root of the tree (which must be black) and recursively consider the number of red nodes in the left and right subtrees and show by induction that this holds. But I can't seem to figure out some of the details (and there seem to be some inconsistencies).

Answer 1

Deposit 3 dollars on each red nodes initially.

For each black node, if it is a sibling or a child of a red node, move one dollar on that red node onto the black node.

Claim 1: there is at most one dollar on each black node. There is no dollar on the root of the tree.

Claim 2: there is no dollar on red nodes.

The total amount of dollars was $3\times\#\text{red nodes}$ initially. The total amount of dollars at the end is at most $\#\text{black nodes} - 1$. $$3\times\#\text{red nodes} \le \#\text{black nodes} - 1$$ which means $4\times\#\text{red nodes} \le (\#\text{black nodes} + \#\text{red nodes}) - 1=\#\text{all nodes}-1$.

I will let you prove the two claims.