「They believed proved that her hair was dyed brown」だけなら、文章として間違っています。They believedかprovedのどれか一つにしないとダメです。
ググったら、以下の文章があったのですが、これであればOKです。
But school staff who inspected her hair said she had black roots, which they believed proved that her hair was dyed brown.
which they believed proved⇒彼らがそれが証明すると確信していた
他の簡単な例で示すと:This they believed proved her innocence. (これが彼女の無罪である証拠となったと確信した)
This they thought proved her innocence のような、think(と思う)と同じ使い方です。