Sachverhalt: A. Am 28. Januar 2015 lehnte die Ausgleichskasse des Kantons Solothurn den Anspruch von A._ auf Familienergänzungsleistungen infolge fehlender Bedürftigkeit ab. Mit Einspracheentscheid vom 31. Juli 2015 begründete sie die Abweisung damit, bereits die von ihm getrennt lebende Mutter seines Sohnes beziehe Familienergänzungsleistungen. B. Das Versicherungsgericht des Kantons Solothurn vom 24. Mai 2016 wies die dagegen erhobene Beschwerde ab, soweit es darauf eintrat. C. A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, es seien der vorinstanzliche Entscheid und die Verfügung vom 28. Januar 2015 aufzuheben und es sei festzustellen, dass die Anwendung der kantonalen Norm gegen Art. 8 Abs. 3 BV verstosse, indem bei gemeinsamer elterlicher Sorge und hälftig geteilter Obhut für den Anspruch auf Ergänzungsleistungen (recte: Familienergänzungsleistungen) auf das Kriterium des Geschlechts (Mutter) abgestellt werde. Zudem sei festzustellen, dass er, welcher die Obhut und elterliche Sorge gemeinsam mit der Mutter ausübe, grundsätzlich Anspruch auf Ergänzungsleistungen (recte: Familienergänzungsleistungen) habe, sofern die übrigen Voraussetzungen erfüllt seien. Schliesslich beantragt er, die Ausgleichskasse sei anzuweisen, seinen Anspruch auf Familienergänzungsleistungen unter Berücksichtigung der hälftigen Auslagen für das Kind neu zu berechnen. Die Ausgleichskasse schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz beantragt ebenfalls die Abweisung der Beschwerde.