I had the same problem. I solved it by following those steps :
1/ First, you have to connect your firebase account > firebase login
2/ Next, check if the connection is alright (you need to create your project on firebase in a first place to see it in the result) > firebase projects:list
3/ Then, you need to initialize firebase > firebase init
4/ And now you can add the following command > ng add @angular/fire