How to fix Database might contain bulk logged changes that have not been backed up for Always On

Question: I'm trying to add a new database to an existing Clustered Always On High Availability Group , but every time I execute the following  statement , I get the error message below

alter availability group MY_AG1 add database [mydb];

Msg 1475, Level 16, State 105, Line 5
Database "mydb" might contain bulk logged changes that have not been backed up. Take a log backup on the principal database or primary database. Then restore this backup either on the mirror database to enable database mirroring or on every secondary database to enable you to join it to the availability group.

Answer: After creating the database, if you don't do a FULL backup, even though the database is in FULL recovery mode, it is still in pseudo SIMPLE RECOVERY mode , until you've taken the first FULL BACKUP to create a new backup chain. 

The way to fix the problem is to create the FULL BACKUP and then proceed with adding to the AVAILABILITY GROUP.   It has to be a bona fide FULL BACKUP without the copy only option.

Read more on Always On

Quick access to SQL Server AlwaysOn Availability cheatsheet