A forma correta é «Tenho a certeza de que vamos...».

A dúvida da consulente deve-se ao facto de se verificarem muitos casos de supressão da preposição de que o nome/substantivo certeza impõe no argumento, tal como observaram João Peres e Telmo Móia em Áreas Críticas da Língua Portuguesa (Lisboa, Caminho, 1995, pp. 110-111): «O tipo de supressão de preposições argumentais [...] corresponde a um fenómeno bastante difundido – como bem demonstra a quantidade de casos recolhidos –, que muitos dicionários e gramáticas registam, que encontramos em muitos dos nossos autores e que parece ser aceite por grande parte dos falantes.»

No entanto, apesar de não considerarem que essa omissão torne tais estruturas agramaticais, os dois defendem o favorecimento da «norma da conservação da preposição nos casos em preço».

Segundo Peres e Móia, os nomes/substantivos certeza ou ideia e os adjetivos certo, seguro, indeciso e hesitante requerem a preposição argumental de.

Repare-se nos seguintes exemplos:

1. «Tenho a certeza de que o Paulo me vai ajudar.»

1.1. (?) «Tenho a certeza que o Paulo me vai ajudar.»

2. «Tenho a certeza de poder contar com a ajuda do Paulo.»

2.1. *«Tenho a certeza poder contar com a ajuda do Paulo.» (* – agramatical)

3. «Tenho a certeza de muitas coisas.»

3.1. *«Tenho a certeza muitas coisas.» (* – agramatical)

4. «Tenho a certeza disso.»

4.1. *«Tenho a certeza isso.» (* – agramatical)

Portanto, não há dúvida de que a utilização da preposição de torna a frase correta, havendo a obrigatoriedade do seu emprego «antes de argumentos oracionais infinitivos (2) e de argumentos nominais (3) e pronominais (4).