I - Par récurrence :

la proposition est vraie pour n = 1.

Supposons qu'elle soit vraie au rang n, alors on a q(n) =n*4^(n+1)-(n+1)*4^n+1 = 9*p(n) ou p(n) est un entier.

au rang n+1, q(n+1) = (n+1)*4^(n+2) - (n+2)*4^(n+1)+1 = 4*q(n) + 3*(4^(n+1) - 1)

Pour que q(n+1) soit multiple de 9 pour tout n, il suffit que 4^(n+1) - 1 soit multiple de 3

On montre que ceci est vrai par récurrence, avec la décomposition : 4^(n+1) - 1 = 3*4^n + 4^n - 1.

II - Avec des congruences :

f(n) = n*4^(n+1)-(n+1)*4^n+1 = 1 + (3n-1)*4^n.
Remarquons que 4^1 = 4 mod 9 ; 4^2 = 7 mod 9; 4^3 = 1 mod 9...
Si n = k mod 3, alors 3n-1 = 3k-1 mod 9, 4^n = 4^k mod 9 et donc f(n) = f(k) mod 9.
Il suffit de vérifier que cela fonctionne pour 3 entiers consécutifs (f(0) =0; f(1) = 9; f(2) = 81).

x = n*4^(n+1)-(n+1)*4^n+1 = (3n-1)*4^n + 1
si n = 3k, alors 4^n = 64^k = 1 mod 9 et 3n-1 = 9k - 1 = 8 mod 9 et x = 0 mod 9
si n =3k+1, alors 4^n = 4*64^k = 4 mod 9 et 3n-1 = 9k+2 = 2 mod 9 et x = 0 mod 9
si n = 3k+2, alors 4^n = 16*64^k = 7 mod 9 et 3n - 1 = 9k + 5 = 5 mod 9 et x = 0 mod 9.

III - Avec une suite :

On pose u_n=n*4^(n+1)-(n+1)*4^n +1
On vérifie que
u_(n+1)-u_n =9*(n+1)*4^n
En sommant u_n=9*{sum((k+1)*4^k; k=0...n-1}+u_0 avec u_0=0
soit u_n est divisible par 9

IV - Une généralisation du problème :

Démontrons plus généralement que pour tous entiers p > 0 , n >=0 , m >= -n :
A = n*((p+1)^(n+m)) - (n+m)*((p+1)^n) + m est divisible par p^2.
(Le problème proposé est le cas particulier p=3 , m=1)

La démonstration repose sur la relation (p+1)^q == p*q+1 (modulo p^2), 
que l'on obtient facilement à partir de la formule du binôme.
Et alors on a tout de suite :
A == n*(p*(n+m)+1) - (n+m)*(p*n+1) + m == 0 (modulo p^2) , q.e.d !