Wrong Battery Indicator after upgrading to 10.1

Recently, after updating from iOS 9 to 10.1 I face the following issue: the phone when I open it up, it will be at 20-30% (or a different %), and then a second later it’s shutting down and giving me the “plug in” screen.
Let me tell you that I have "Reset All Contents and Settings" and when came back, I setup as "A New iPhone", instead of restoring any backup. However, the problem with the inaccurate battery indicator persists. Hard reset also performed; not fix, though.

Steps:
1. Battery Indicator at least 20% (e.g. 34%)
2. Turn off the phone.
3. Turn on the phone.
4. Home screen appears.
5. Second later the phone shuts down.
6. Plug-in screen appears.
7. Plug-in charger
8. The phone is being charged from the previous indication (from 34%)

P.S. I don't feel that there is a difference in the battery life (seems normal, as before). However, I have no clear picture what is the current battery status.

P.P.S. This phenomenon ALSO happened when I bought my iPhone and setup iOS 9 using backup from precious phone (iPhone 4s). However, when I did a Reset to All Contents and Settings, and setup As A New Device, everything came back to normal.